MySQL索引原理

众所周知，MySQL的InnoDB引擎采用B+树作为索引结构，为什么呢？

概述

InnoDB存储引擎支持两种常见的索引：B+树索引、哈希索引。

• 哈希索引
  • 自适应
  • InnoDB存储引擎根据表的使用情况自动为表生成哈希索引，不能人为干预
• B+树索引
  • 构造类似于二叉树
  • 根据键值快速找到数据
  • B为Balance，因为B+树最早从平衡二叉树演化而来，但是B+树不是一个二叉树

B+树索引并不能找到一个给定键值的具体行。找到的只是被查找数据行所在的页。然后数据库通过把页读入内存，再在内存中进行查找，最后得到查找的数。

历史

B+树是由二叉查找树(左<根<右) -> 二叉树(也称AVL树，二叉树的基础上，满足任何节点的左右两个子树共度最大差为1) -> B树，变化而来。

• 二叉树缺点：只规定了简单结构，存在多种深度可能，导致二叉树的效率低，所以引入了平衡二叉树。
• 红黑树与AVL树类似，都是在进行插入和删除时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。在Java中TreeSet、TreeMap的底层就是用的这个方法。
  • 节点是红色或黑色
  • 根节点是黑色
  • 叶子节点（nil,空节点）是黑色
  • 每个红色节点的两个子节点都是黑色
• B通常理解成是Balance的意思，B- tree 就是B树，简称平衡树。
  • B树是平衡多路查找树（有多个查找路径，不止2个），是一种平衡的多叉树。因为B树是平衡树，每个节点到叶子节点的高度都是相同的，这样可以保证B树的查询是稳定的。
  • 使用B树可以显著减少定位记录时所经历的中间过程，从而快速定位，加快存取速度。
  • 与二叉树相比，B-tree利用多个分支（二叉树只有2个分支）节点，减少了获取记录时所经历的节点数，从而达到节省存取时间的目的。
    • 每个节点的关键字增多了，特别是B树应用到数据库中的时候。
    • 所有的页节点都在同一层上

数据库充分利用了磁盘块的原理（磁盘数据的存储采用的是块的形式进行存储，每个块的大小一般为4k,每次去取数据的时候，就是取出这个4k的大小，而不是只取出想要的大小。就是说每次IO的时候，同一磁盘块的数据都是一次性提取出来）。把树的节点关键字增多后，树的层级比原来二叉树的层级少了，这样就可以减少数据查找的次数 ，降低复杂度了。

• B+ Tree 是在 B树基础上的优化，使其更适应存储索引结构
  • B树的结构中，每个节点不仅包括数据的key值，也包括data值。而每一页的存储空间都是有限的，如果data数据较大的时候，会导致每一页中存储的key比较少，当存储的数据量比较大时，同样会导致B树的查询深度很大，增加磁盘IO次数，进而影响查询效率
  • B+ Tree中，非叶子节点上只存储key的信息，这样可以加大每一页中存储key的数量，降低B+ Tree的高度。
    • 非叶子节点只存储key信息
    • 所有叶子节点之间有一个链指针
    • B+树的非叶子节点只进行数据的索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样。
    • B+树的应用场景主要是数据库索引结构，数据库的查询有时候可能一次多条，如果分布在不同的层（树的层级），那么在取出数据后，还需要做排序。而在一个层级上，且有指针连接各个叶子节点也使得查询效率更高。

B树查找过程

假设每一个磁盘页正好存放一个B树的节点，而子树的指针就是存放另一个磁盘页的地址。

那么查找操作就是：

• 首先从根节点(从磁盘调出数据，进行第一次磁盘I/O，数据读入内存进行查找)，内存中可以顺序也可以二分，如果找到要查找的那个数则停止，否则要确认指针的位置，也就是确认是那颗子树，然后递归下去。

B树与B+树

首先要明确，B表示balance，B树是一种多路自平衡的搜索树。

B树的每一个节点最多包含k个孩子，k被称为B树的阶，k的大小取决于磁盘页的大小。

B树类似于平衡二叉树，不同的是B树允许每个节点有更多的子节点。

B树特点

• 所有键值分布在整棵树中
• 任何一个关键字出现且只出现在一个节点中
• 搜索有可能在非叶子节点结束
• 在关键字全集内做一次查找，性能逼近二分查找

根据B树的定义，可知检索一次最多需要访问h个节点。根据上面的局部性原理和磁盘预读，B树中用了这个技巧：每次新建节点时，直接申请一个页的空间，这样就保证了一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需要一次I/O。

B树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁（比如查询某段时间之内的数据）的，而B树不支持这样的操作或者说效率太低（前文已经说明效率低的原因）

B树中一次检索最多需要h-1次I/O(根节点常驻内存)，渐进复杂度$$O(log_d^N)$$。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小(通常不超过3)。红黑树这种结构，h要深的多。逻辑上很近的节点(父子)物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度为O(h)，效率明显比B树差很多。

B+树

B+树是B树的变种，也是一种多路搜索树，与B树的不同点在于：

• 所有关键字存储在叶子节点出现，内部节点(非叶子节点并不存储真正的data)
• 为所有叶子节点增加了一个链指针，就形成了带有顺序访问指针的B+树（提高区间访问性能）
• 每个节点的指针上限为2d
• 由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。

为什么选择B+树

• B+树更适合外部存储，由于内节点无data域(负责索引)，一个节点可以存储更多的内节点，每个节点能索引的范围更大更精确，也意味着B+树单次磁盘I/O的信息量大于B树，I/O效率更高。
• MySQL是一种关系型数据库，区间访问时常见的一种情况，B+树叶节点增加的链指针，加强了区间访问性，可使用在范围区间查询等。而B树每个节点key和data在一起，则无法区间查找，因为需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

为什么不用二叉查找树实现

MySQL是基于磁盘的数据库系统，索引往往以索引文件的形式存储在磁盘上。因为数据量很大的时候索引文件大小可能达到几个G。所以在利用索引查询时，不能把整个索引全部加载到内存，只能逐一加载每一个磁盘页(对应着索引树的节点)，修改之后又写回到磁盘。索引查找过程就要产生磁盘I/O，比内存操作要高几个数量级，所以MySQL索引的结构就要尽量减少查找过程中磁盘I/O的存取次数。

二叉查找树的时间复杂度为O(longN)，从算法逻辑上讲查找速度和比较速度都是最小的。但是要考虑磁盘I/O，节约在磁盘上花的时间，对搜索树的性能提高是最有效的，所以文件系统及数据库系统普遍采用B树或B+树作为索引结构。

索引的本质

在使用数据库时，查询是最主要的功能之一。所以需要查询数据的速度尽可能的快，所以数据库的设计者会从查询算法的角度进行优化。

最基本的查询算法当前是顺序查找，但复杂度为O(n)会使得在数据量很大时效率很差。一些其他查找算法，诸如二分查找或二叉树查找效率更高，但每种算法都只能应用于特定的数据结构之上。例如，二分查找要求被检索的数据有序，而二叉树查找只能应用于二叉查找树。所以，在数据之外，数据库还维护着满足特定查找算法的数据结构，这些数据结构以某种个方式指向数据，这样就可以实现高级查找算法。这种数据结构，就是索引。

例子

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条数据，最左边是数据的物理地址（逻辑相邻的记录在磁盘上的物理存储地址并不一定是相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录的物理地址指针，这样就可以运用二叉查找在O(logN)的复杂度内获取到相应数据。虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或红黑树实现的，为什么呢？

磁盘存取原理

磁盘是块设备。也就是说磁盘的读写单位是以块为单位，一般块大小从0.5K到4K。

一个扇区512byte，也就是0.5K，一页是4K，那就是一页是8个扇区的大小。

即使只读取一个字节，磁盘也会将包含该字节的所有数据读取。其中，最占用时间的是磁盘的寻道，也就是磁头在盘片上找到需要读取的块所在的位置，而在磁盘上顺序读取数据所花的时间是占比比较小的。

磁盘如何读取

由于磁盘的读取速度与内存之间的鸿沟，为了提高效率，磁盘在读取数据时，每次都会预读。磁盘在读取完需要的数据，会顺序向后读一定长度的数据放入内存，为什么要预读？

局部性原理

当一个数据被用到时，其附近的数据也通常会马上被使用，程序运行期间所需要的数据通常比较集中。

预读

磁盘顺序读取的效率很高(无寻道时间，只需很少的旋转时间)。所以对于有局部性的程度来说，预读可以提高I/O效率。

预读的长度一般为页(Page)的整倍数。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相扽的块，每格存储块称为一页。

MySQL(默认使用InnoDB引擎)，将记录按页的方式进行管理。每页大小默认为16K。Linux默认页大小为4K。

要减少磁盘上花的时间，就可以从减少读盘次数以及减少寻道时间着手。B树采取的方法就是，充分的利用盘块的空间，在一个盘块种尽可能多得存储信息，或者在连续的盘块地址上存储尽可能多的信息。在数据结构上的变化就是每个节点存储多个key信息以及包含多个子节点。

磁盘的I/O次数由树的高度决定的。在最坏的情况下磁盘的I/O数等于索引树的高度。而B树是一颗平衡的m-路查找树，假设高度为h，每一个节点最多容纳m-1个关键字，所以一颗m-路查找树总共可容纳$$m^k-1$$个关键字。与二叉查找树比较，当高度为h，能容$$2^h-1$$个关键字，若高度为3，则二叉查找树只能容纳7个关键字，而对于200-路查找树可容纳$$200^3-1$$个关键字。

为了减少磁盘的I/O次数，就需要把原来”瘦高”的树结构变得”矮胖”，而这正满足B树的特质之一，内节点出度d越大，索引的性能越好，而出度的上限取决于节点内key和data的大小：$$d_{max}=floor(pagesize/(keysize+datasize+pointsize))$$

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，在MySQL中主要为MyISAM和InnoDB两个存储引擎的索引实现。

MyISAM索引实现

MyISAM引擎使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址。索引文件和数据文件分离，索引文件仅保存数据记录的地址。

假设以Col1为主键，则上图是MyISAM表的主索引示意。MyISAM的索引文件仅仅保存数据记录的地址。

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

同样也是B+树，data域保存数据记录的地址。

因此，MyISAM中索引检索的算法为：

• 按照B+树搜索算法搜索索引，如果指定的key存在，则取出其data域的值
• 以data域的值为地址，读取相应数据记录

MyISAM的索引方式也叫做”非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

InnoDB也是用B+树作为索引结构，但实现方式与MyISAM不同。

InnoDB的数据文件本身就是索引文件。表数据文件本身就是按B+树组织的一个索引结构，叶节点的data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。

• 因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MyISAM可以没有)。

如果没有显式制定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

• InnoDB的辅助索引data域存储相应记录主键的值而不是地址。
  • InnoDB的所有辅助索引都引用主键作为data域

聚集索引Clustered Index

• 按照主键构建B+树
• 叶子节点：存放的是数据表的行记录的数据
  • 数据页
  • 用双向链表进行关联，按照主键顺序排列

辅助索引Secondary Index(非聚集索引)

• 叶子节点除了存储键值信息外，在索引行还包含了bookmark，也就是找到索引对应的行数据

问题：为什么不建议使用过长的字段作为主键？

所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大

问题：为什么不建议使用非单调的字段作为InnoDB的主键

InnoDB数据文件本身是B+树，非单调的主键会造成在插入新纪录时数据文件为了维持B+树的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

索引使用及优化

高效使用索引的首要条件是知道什么样的查询会使用到索引

• MySQL优化
  • 结构优化Scheme optimization
  • 查询优化Query optimization

---

MySQL官方提供了示例数据库

$ git clone git@github.com:datacharmer/test_db.git
$ cd test_db
$ mycli < employees.sql

因为是在本地测试，所以用户名和host都可以省略，直接敲密码即可。执行后会有下面的输出：

INFO
CREATING DATABASE STRUCTURE
INFO
storage engine: InnoDB
INFO
LOADING departments
INFO
LOADING employees
INFO
LOADING dept_emp
INFO
LOADING dept_manager
INFO
LOADING titles
INFO
LOADING salaries
data_load_time_diff
NULL