多列索引结构和原理

迷南。 2022-06-14 10:22 99阅读 0赞

### 索引的数据结构 ###

前面讲了生活中索引的例子，索引的基本原理，数据库的复杂性，又讲了操作系统的相关知识，目的就是让大家了解，任何一种数据结构都不是凭空产生的，一定会有它的背景和使用场景，我们现在总结一下，我们需要这种数据结构能够做些什么，其实很简单，那就是：每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢？就这样，b+树应运而生。

### 详解b+树 ###

如上图，是一颗b+树，关于b+树的定义可以参见[B+树][B]，这里只说一些重点，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

### b+树的查找过程 ###

如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

### b+树性质 ###

1.通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

2.当**b+树的数据项是复合的数据结构**，比如(name,age,sex)的时候，b+数是按照从*左到右的顺序来建立搜索树*的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，**如果name相同再依次比较age和sex**，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。*比如*当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，*所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了*， 这个是非常重要的性质，即**索引的最左匹配特性**。

# 慢查询优化 #

关于MySQL索引原理是比较枯燥的东西，大家只需要有一个感性的认识，并不需要理解得非常透彻和深入。我们回头来看看一开始我们说的慢查询，了解完索引原理之后，大家是不是有什么想法呢？先总结一下索引的几大基本原则

## 建索引的几大原则 ##

1.最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

2.=和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

3.尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(\*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录

4.索引列不能参与计算，保持列“干净”，比如from\_unixtime(create\_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create\_time = unix\_timestamp(’2014-05-29’);

5.尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可

## 回到开始的慢查询 ##

根据最左匹配原则，最开始的sql语句的索引应该是status、operator\_id、type、operate\_time的联合索引；其中status、operator\_id、type的顺序可以颠倒，所以我才会说，把这个表的所有相关查询都找到，会综合分析；  
比如还有如下查询

<table style="border:1px solid silver; width:810px; border-collapse:collapse; word-break:break-word; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:12px!important; min-height:auto!important; background:none!important"> 
 <tbody style="border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important; background:none!important"> 
  <tr style="border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important; background:none!important"> 
   <td style="border:1px solid silver; padding:3px; border-collapse:collapse; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:35px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(175,175,175)!important; background:none!important"> 
    <div style="border-width:0px 2px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px 0.5em!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important; background:none rgb(244,244,244)!important">
      1 
    </div> 
    <div style="border-width:0px 2px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px 0.5em!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important">
      2 
    </div> </td> 
   <td style="border:1px solid silver; padding:3px; border-collapse:collapse; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important"> 
    <div style="border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important; background:none!important"> 
     <div style="border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px 1em!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important; background:none rgb(244,244,244)!important"> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">select</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">* </code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">from</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">task </code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">where</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">status = 0 </code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:gray!important; background:none!important">and</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">type = 12 limit 10;</code> 
     </div> 
     <div style="border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px 1em!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:auto!important"> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">select</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(255,20,147)!important; background:none!important">count</code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">(*) </code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">from</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">task </code> 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; color:rgb(0,0,255)!important; background:none!important">where</code>&nbsp; 
      <code style="white-space:pre-wrap; border:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.8em!important; margin:0px!important; outline:0px!important; overflow:visible!important; padding:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:auto!important; background:none!important">status = 0 ;</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

那么索引建立成(status,type,operator\_id,operate\_time)就是非常正确的，因为可以覆盖到所有情况。这个就是利用了索引的最左匹配的原则

分类:  [mys][]

[B]: http://zh.wikipedia.org/wiki/B%2B%E6%A0%91
[mys]: http://www.cnblogs.com/dreamworlds/category/814523.html