微信大牛教你深入了解数据库索引

　　| 作者刘国斌，腾讯微信事业群研发工程师，目前从事企业微信的后台研发工作，已经参与企业微信消息系统、群聊、客户联系等企业微信多个核心功能的迭代。
　　数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。
　　最基本的查询算法当然是顺序查找（linear search），然而这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。
　　如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
　　作为一种数据结构，索引专为加快查找速度而设计。索引本质上就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项组成，每个索引至少包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
　　PartⅠ 索引数据结构
　　索引主要分为线性索引、树形索引和多级索引。下面将简单介绍一些基础的索引实现方式以引出MySQL的索引实现。
　　1.1 线性索引
　　所谓线性索引就是将索引项集合组织为线性结构，也成为索引表。虽然MySQL常使用树形索引，但是线性索引的有些性质和树形索引是相通的，所以先简单介绍一下两种比较常见的线性索引。
　　1.1.1 稠密索引
　　稠密索引在线性索引中，将数据记得每一条记录都对应一个索引项，并维护一个索引表。由于在真实环境中可能需要应对大量的数据，所以对于稠密索引的索引表来说，索引项一定是按照关键码有序的排列。
　　索引项有序就意味着可以直接对索引表进行像二分查找、插值查找、斐波那契查找等高效率的查找操作，大大减少查询的时间复杂度。
　　但是稠密索引也有一个明显的缺点，对于大量数据状态下索引表会变得非常的长，如果全部取出内存的话将会占用大量内存空间。
　　1.1.2 分块索引
　　为了解决稠密索引带来的问题于是就有了分块索引。分块索引是稀疏索引的一种，把数据记得记录分成了若干块，，实现了分块有序，这些块满足以下两个条件：
　　第一个是块间有序，例如要求第二块所有记录的索引关键字均大于第一块中所有的记录关键字，第三块要大于第二块的。
　　第二个是块内无序，块内的记录可以瞎排虽然可以实现块内有序，但是这就造成了和稠密索引一样的问题。
　　对于分块有序的数据将每块建立一个索引项，这种索引方法叫做分块索引。分块索引的索引项结构可以如下：
　　最大关键字，用于存储每一块的最大关键字，可作为这一块所有数据的关键字范围的依据；
　　块记录个数，方便遍历块数据；
　　用于指向块首数据的指针，用于遍历块。
　　使用分块索引，即使是遍历索引列表再遍历对应的块，也要比直接遍历全部数据效率高，而且对于有序的索引列表还可以使用更高效的查找算法。总的来说，对细分快不需要有序的情况下，分块索引兼顾了空间效率和时间效率，大大增加了整体查找的速度，所以也被普遍运用于数据库表的查找技术应用中。
　　1.2 树形索引
　　1.2.1 二叉树、平衡二叉树和红黑树索引
　　线性索引在插入和删除上就要浪费大量的时间，这点对于数据量大的情况下尤为明显。所以MySQL的引擎几乎没有使用线性索引。MySQL的主流存储引擎都使用B-/B+树索引，作为二叉树的变种，我们先简单介绍一下使用二叉搜索树构建的索引。
　　二叉搜索树（binary search tree）又称为二叉查找树，它或者是一棵空树，要么是具有以下性质的二叉树：
　　若该树左子树不为空，则左子树上所有节点值均小于其根节点；
　　若该树右子树不为空，则右子树上所有节点值均大于其根节点；
　　该树的左右子树也是二叉搜索树。
　　一个可能的二叉树索引如下：
　　二叉树在保留了二分搜索的前提下，使插入和删除上可以直接修改指针实现，极大提高插入和删除的效率。但是由于二叉树的形状不确定性导致极端查询时间复杂度和平均查询时间复杂度相差很大。例如如果插入数据时本身就是从小到大插入的，那么在构建索引时就会构建出一条极右斜树，他虽然是二叉搜索树，但是这时候对索引的搜索效率等于遍历效率，即O(n)，而对于上图情况却最多只需要查找两次。所以就有了平衡二叉树(AVL tree)和红黑树(Red–black tree)
　　平衡二叉树上所有结点的平衡因子（balance factor）值只能是-1、0、1，保证了查找时的效率问题，但是同样的由于频繁调整树的节点，插入和删除效率下降。而红黑树并不追求＂完全平衡＂——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
　　红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较＂便宜＂的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
　　1.3 B-/B+树索引
　　B树(B-树)是为了磁盘或其它存储设备而设计的一种多路平衡查找树，其本质就是使用[key, balue]结构构建出查找路线，key为记录的键值(即索引值)，value对应不同数据记录。可以使用度和阶来定义B树。这里使用阶来定义：节点最大的孩子书目称为B树的阶。
　　一个m阶的B树具有如下性质：
　　如果根节点不是叶子节点，则其最少有两棵子树；
　　设(m/2) ≤ k ≤ m，则每个根的分支节点都有k-1个元素和k个孩子，每个叶子节点n都有k-1个元素；
　　所有叶子节点深度相同且等于树高h；每个非终端结点中包含有n个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
　　Ki(i=1...n)为关键字，且关键字按顺序升序排序K(i-1) < Ki
　　Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)
　　关键字的个数n必须满足(m/2)-1 <= n <= m-1
　　一个示例B树结构：
　　由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到指针，前者查找成功，后者查找失败。伪代码参考如下：
　　BTree_Search(node, key) { if(node == ) return ; foreach(node.key) { if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i+1]->node);}data = BTree_Search(root, my_key);
　　关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。
　　B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，因为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。
　　B树解决了树深问题，但如果每个节点在磁盘的不同页，B树还是需要在硬盘的页面进行多次访问才能遍历所有元素， 为了解决这个问题就有了B+树，与B-Tree相比，B+Tree有以下不同点：
　　每个节点的指针上限为2d而不是2d+1；
　　分支节点类似索引key，只存储其子树中最大或者最小的节点；
　　叶子节点包含全部关键字信息及指向其的指针；
　　出现在分支节点的元素会被追加到该分支节点位置的中序后继者中。
　　一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针，如下图。
　　所以要遍历的时候直接使用链表，要查找的时候从树根查找。B+树的结构特别适合带有范围的查找，可以从根节点找到范围左边界的数据，然后再遍历到右边界即可。
　　PartⅡ MySQL中的B-TREE索引
　　2.1 MySIAM索引实现
　　MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
　　这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，如图：
　　同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
　　MyISAM的索引方式也叫做＂非聚集＂的，之所以这么称呼是为了与InnoDB的聚集索引区分。
　　2.2 InnoDB索引实现
　　InnoDB也使用B+Tree作为索引结构，但具体实现依然是有差异的。
　　第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
　　上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
　　第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
　　这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
　　了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
　　2.3 为什么使用B-/B+树
　　我们上面提到的所有索引数据结构，除了分块索引以外，其他的索引查找，都需要把所有的数据行都建立索引，索引索引本身会特别大，不可能全部存储在内存中。因此索引一般是以文件的形式存储在硬盘里。
　　2.3.1 主存存取
　　计算机的主存基本都是随机访问存储器(Random-Access Memory，RAM)，其分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM快，但是也贵的多，一般作为CPU的高速缓存，DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机器操作，所以访问速度非常快。他们是易失的，即如果断电，保存DRAM和SRAM保存的信息就会丢失。
　　2.3.2 磁盘存取
　　磁盘空间动辄百GB级的容量以及低廉的价格使得磁盘成为数据的主要存储区，但是磁盘存取相对于主存来说却多了一些额外的步骤导致效率远不如直接读写主存。因为磁盘涉及到机器操作，读取速度一般为毫秒级，从DRAM读速度比从磁盘度快10万倍，从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构以分析磁盘读写原理。
　　磁盘由盘片构成，每个盘片有两面，又称为盘面(Surface)，这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(spindle)，他使得盘片以固定的旋转速率旋转，通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM。磁盘包含一个或多个这样的盘片并封装在一个密封的容器内。每个磁盘表面是由一组成为磁道(track)的同心圆组成的，每个磁道被划分为了一组扇区(sector)。每个扇区包含相等数量的数据位，通常是（512）子节。扇区之间由一些间隔(gap)隔开，间隔不存储数据。
　　每两个磁盘之间有一个传动臂，负责在其上磁盘的下盘面和其下磁盘的上盘面读取信息。所以如图中所示磁盘结构的话，有四个盘面用来存储数据。每个传动臂都有一个读写头用于读写磁道上扇区中的数据。完成一次磁盘读写，需要以下三个步骤：
　　寻道: 如图，传动臂沿着磁盘半径前后移动（实际是斜切向运动），驱动器可以将读写头定位到任何磁道上，每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）一般硬盘的平均寻道时间在7.5～14ms。磁盘地址 = 台号+柱面号+盘面号+扇区号；
　　旋转：读写头移动到指定磁道后，磁盘通过转动，将对应扇区移动到读写头下方（或上方，看盘面）；
　　传送：数据通过系统总线传送到内存的时间，一般传输一个字节(byte)大概0.02us=2*10^(-8)s。
　　设完成一次磁盘读写的时间为T，则有：T = t1 + t2 + t3
　　2.3.3 预读和局部性原理
　　由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
　　当一个数据被用到时，其附近的数据也通常会马上被使用；
　　程序运行期间所需要的数据通常比较集中。
　　由于不需要寻道时间，只需很少的旋转时间，所以磁盘顺序读取的效率很高，因此对于具有局部性的程序来说，预读可以提高I/O效率。
　　预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。MySQL中也有页的概念，而且一般也为页的整倍数。例如Innodb引擎中一页为16k。
　　2.3.4 B/B+树对于二叉树等索引的性能分析
　　综上所述，一般使用磁盘I/O次数评价索引结构的优劣。
　　从B-Tree分析，设由树高为h的m阶B树，根据B树的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
　　通过控制B树的阶（或度），实现在新建节点时直接申请一个页的空间，保证一个节点物理上也存储在一个页里，由于计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
　　由于根节点常驻内存，B-Tree中一次检索最多需要h-1次I/O，时间复杂度为O(h)=O(logm N)。一般实际应用中，阶数m是非常大的数字，通常超过100，因此树高h非常小（通常不超过3）。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O时间复杂度也为O(h)，效率明显比B-Tree差很多。
　　综上所述，用B-Tree作为索引结构效率是非常高的。
　　而且B+Tree更适合外存索引，原因和内节点阶数m有关。从上面分析可以看到，在一定范围内，m越大索引的性能越好，而出度的上限取决于节点内key和data的大小：
　　dmax=floor(pagesize/(keysize+datasize+pointsize))
　　floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
　　但是阶数并不能无限增长，否则会造成索引表不在同一页而降低效率，而且当阶数太大，在遍历某个索引节点时效率会退化为近似于顺序遍历。
　　2.4 B+树最左前缀原理
　　对于多级索引(a,b,c)，对于 a > 0 and b = 1这种查询，不能用到索引，作为最左前缀原理。
　　在B+树构建时，其顺序是先以a的顺序排列，然后再以b的顺序排列，依次类推，所以如果对a进行范围查询，那么无法再次对其余两列进行匹配。
　　如果从左到右遍历一颗B+树索引，可能如下：(1,a,x)(1,a,y)(1,b,x)(1,b,y)(1,c,x)(1,c,y)(2,a,x)(2,a,y)(2,b,x)(2,b,y)(2,c,x)(2,c,y)
　　PartⅢ 散列表查找（哈希查找）
　　B/B+树作为索引，所有只会访问或者修改一条数据的 SQL 的时间复杂度都是O(log n)。也就是树的高度，但是使用哈希却有可能达到 O(1) 的时间复杂度，看起来散列表查找效率特别美好。
　　但是如果我们使用哈希作为底层的数据结构，遇到order by、大于小于、更新索引列的值等场景时，使用哈希构成的主键索引或者辅助索引可能就没有办法快速处理了。
　　散列表对于处理范围查询或者排序性能会非常差，只能进行全表扫描并依次判断是否满足条件，也就意味着我们使用的索引对于这些查询没有其他任何效果，最终的性能可能都不如从日志中顺序进行匹配。
　　另外散列表的存储是尽量将数据打散到一个区间，打散的存储对于磁盘读写来说也是非常的不友好。因此对于MySQL的Innodb，只有少量读取请求会使用散列表优化读取速度，大部分情况，还是使用B+树。