MySQL索引高级

　　一. 索引

　　在上一章节中健哥讲解了索引的基本入门和使用进阶。那么在这一节中我们来探讨下索引的深层原理。各位小伙伴准备好了吗，我们开始喽!

　　索引的实现原理

　　索引是在MySQL的存储引擎中实现的，所以每种存储引擎的索引也就各不相同了，不同的存储引擎支持不同类型的索引。这里我们主要研究InnoDB引擎实现的B+树索引。

　　B+树是一种数据结构。通常使用在数据库和操作系统中的文件系统，特点是能够保持数据稳定有序，还能够加快查询速度，我们一起来看下吧。

　　磁盘存储

　　系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的。

　　位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

　　InnoDB存储引擎中有页(Page)的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB。

　　InnoDB引擎将若干个地址连接磁盘块，以此来达到页的大小16KB，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

　　BTree

　　BTree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述BTree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。BTree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的BTree：

　　根据图中结构显示，每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

　　查找顺序,模拟查找15的过程 ：

　　● 根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】比较关键字15在区间(<17)，找到磁盘块1的指针P1。

　　● P1指针找到磁盘块2，读入内存。【磁盘I/O操作第2次】比较关键字15在区间(>12)，找到磁盘块2的指针P3。

　　● P3指针找到磁盘块7，读入内存。【磁盘I/O操作第3次】 在磁盘块7中找到关键字15。

　　● 分析:

　　○ 发现需要3次磁盘I/O操作，和3次内存查找操作。

　　○ 由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个BTree查找效率的决定因素。BTree使用较少的节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

　　4. B+Tree

　　B+Tree是在BTree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

　　从上一节中的BTree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

　　B+Tree相对于BTree区别：

　　● 非叶子节点只存储键值信息。

　　● 所有叶子节点之间都有一个连接指针。

　　● 数据记录都存放在叶子节点中。

　　通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点(即数据节点)之间是一种链式环结构。

　　对B+Tree进行两种查找运算：

　　● 【有范围】对于主键的范围查找和分页查找。

　　● 【有顺序】从根节点开始，进行随机查找。

　　实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在24层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要13次磁盘I/O操作。