数据库索引原理

一、前言

本文主要是阐述MySQL索引机制，主要是说明存储引擎Innodb。
第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。
第二部分结合MySQL数据库中InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。
第三部分讨论MySQL中高性能使用索引的策略。

二、数据结构及算法理论

Innodb存储引擎实现索引的数据结构是B+树，下面介绍几种数据结构，一步步阐述为什么要使用B+树。

2.1 B+树

B+树索引的构造类似于二叉树，根据键值快速找到数据。但是B+树中的B不是代表二叉，而是代表平衡Balance。注意：B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入内存，再在内存中进行查找，最后查到数据。

下面介绍二分查找法：将记录按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，例如：5、10、19、21、31、37、42、48、50、52这10个数，如图所示：

用了三次查找就能找到48。如果是顺序查找的话，则需要8次。对于上面10个数来说，顺序查找的平均查找次数为5.5次，而二分查找法为2.9次，在最坏的情况下，顺序查找的次数为10，而二分查找的次数为4。

二分查找在Innodb中Page Directory中的槽是按照主键的顺序存放的，对于每一条具体记录的查询是通过对Page Directory进行二分查找。

2.2 二叉查找树

数字代表每个节点的键值，二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。通过中序遍历得到键值：2、3、5、6、7、8。

二叉查找树的平均查找次数为2.3次。但是二叉查找树是可以任意构建，如构造如图：

但是这样跟顺序查找就差不多，所以就引用了平衡二叉树的思想，AVL树。

2.3 AVL树

定义：符合二叉查找树的定义，其次必须满足任何节点的左右两个子树的高度最大差为1。

平衡二叉树虽然查找速度非常快但是维护一颗平衡二叉树的代价是非常大，通常需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。

2.4 B+树的特性

B+树是应文件系统而出的一种B树的变形树。在B树中，每一个元素在该树中只出现一次，有可能在叶子节点上，也有可能在分支节点上。而在B+树中，出现在分支节点的元素会被当作它们在该分支节点位置的中序后继者(叶子节点)中再次列出。另外，每一个叶子节点都会保存一个指向后一叶子节点的指针。所有记录都在叶节点，并且是顺序存放，各个叶节点（页为单位）都是逻辑的连续存放，是一个双向循环链表。

如果是要随机查找，就从根节点出发，与B树的查找方式相同，只不过在分支节点即使找到了待查找的关键字，它也只是用来索引的，不能提供实际记录的访问，还是需要到达包含此关键字的终端节点。

如果需要从最小关键字进行从小到大的顺序查找，可以从最左侧的叶子节点出发，不经过分支节点，而是沿着指向下一叶子节点的指针就可遍历所有的节点。

B+树插入必须保证插入后叶子节点中的记录依然排序，所以在插入时必须考虑以下三种情况：

B+树索引在数据库中有一个特点就是其高扇出性，因此在数据库中，B+树高度一般在2-3层，也就是寻找某一键值的行记录，最多2-3次IO，而一般的磁盘每秒至少可以做100次IO，2-3次的意味着查询时间只需0.02-0.03秒。

三、聚集索引、非聚集索引

聚集索引与非聚集索引的区别是：页节点是否存放一整行记录

3.1 聚集索引

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中的数据也是索引一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

实际数据也只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。在许多情况下，查询优化器非常倾向于采用聚集索引，因为聚集索引能够让我们在索引的叶节点直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够快速地访问针对范围值得到查询。查询优化器能够快速发现某一段范围的数据需要扫描。注意每一个页中的记录也是双向链表维护的。

3.2 非聚集索引

也称辅助索引，页级别不包含行的全部数据。页节点除了包含键值以外，每个页级别中的索引中还包含了一个书签，该书签用来告诉InnoDB存储引擎，哪里可以找到与索引相对应的行数据。因为InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引书签就是相应行数据的聚集索引键。下图是聚集索引和辅助索引的关系：

当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到了一个完整的行记录。举例来说：一颗高度为3的辅助索引树中查找数据，那么需要对这颗辅助索引遍历3次找到指定主键；如果聚集索引树的高度同样为3，那么还需要对聚集索引进行三次查找，才能查找一个完整的行数据所在的页，因此需要6次的逻辑Io来访问最终的一个数据页。