学习笔记：mysql索引提升查询效率的底层原理

数据库查询速度慢，很大原因是因为数据存储在磁盘上，而磁盘与内存之间的IO是一项非常耗时的工作，如果没有一个高效的搜索算法，很可能会造成多次磁盘IO，读出了很多盘块后才找到需要查找的数据。而索引是针对这种问题，设计的一种提升数据库查询效率的数据结构，数据库除了要保存的数据之外，会保存索引，借助于这种索引，可以减少磁盘的IO次数。

其实索引可以有很多种实现方式，最简单的一种实现方式就是基于二叉排序树实现的一种索引。

我们假设有这样的一张表：

如果我要查找num=XXX 的某一条记录，如果从表的第一项开始查找的话，当数据量非常大的时候，需要大量的磁盘IO猜才可以找到数据，时间效率很低。

如果我们根据num建立了一个二叉搜索树的话：

二叉搜索树的每个节点存储着索引列Num的值，以及对应的主键，还有表中对应记录的地址。这个例子中由于表只有两列，所以节点存储的是表中记录完整的信息。如果表有多个列的话，则索引二叉搜索树只保存了每个记录的部分信息。Num的值作为索引，在以Num取值作为搜索条件的时候，引导着二叉搜索树索引的遍历搜索。

此时如果要查询Num=30的记录，只需要从二叉搜索树的根遍历到叶子节点即可。目前主流的操作系统使用分页机制，假设二叉搜索树的每个节点是一页的数据，保存在硬盘上。查找Num=30的记录需要进行h次IO将节点输入到内存中来，其中h是二叉搜索树的高度。如果表中的记录按照顺序进行存储的话，和顺序查找大量地进行磁盘IO相比，有效降低了磁盘IO的次数。如果数据库基于二叉搜索树作为索引是完全没问题的，但是实际中很少使用二叉搜索树，原因是因为二叉搜索树每个节点最多只有两个孩子，当节点数很多的时候，树的高度很大，进行查找依然会有很多次的磁盘IO，所以数据库实际的索引是高度小很多的B+树。

MySQL实际的存储结构是这样的，以InnoDB为例，数据文件是以ID为索引建立的一棵B+树（依然假设遍历一个节点进行一次磁盘IO）

这棵B+树即MySQL  InnoDB的底层存储结构。非叶子节点存储主键的值，叶子节点存储完整的一条记录。当数据量非常大的时候，如果要根据ID进行查找的话，仅需要从根节点往下进行搜索到叶子节点即可，由于B+树的高度相对于二叉树很低，所以仅需要少量的磁盘IO就可以搜索到叶子节点。但是如果要查找Num=特定值的记录的话，则需要从第一个叶子节点开始遍历，顺序向后，直到查找到满足条件的记录，这种顺序搜索会造成大量的磁盘IO。所以为了提升查询效率，我们可以根据Num字段再建立一棵索引B+树。B+树的非叶子节点存储Num的值，叶子节点存储Num的值和对应主键的值：

例如，我们要搜索Num=19的记录，从Num索引的B+树的根节点开始遍历，到对应的叶子节点后找到Num=19的记录对应的主键是7。注意Nun索引的B+树叶子节点只存储Num的值和主键的值，如果我们的表有两个以上的字段的话，此时搜索到的数据还是不完整的。需要再次从主键的索引B+树的根节点开始遍历，找到ID=7的叶子节点，从而找到完整的一条记录。磁盘的IO次数是两倍的B+树的高度，当数据量很大的时候，从概率的角度讲，IO次数依然会远远小于顺序遍历叶子节点的IO次数。