这篇文章希望数据库索引的原理对大家有帮助。

第一部分从数据结构和算法理论方面讨论MySQL数据库索引的数学基础。

第二部分结合MySQL数据库的InnoDB数据存储引擎中的索引的构建，实现了讨论集成索引、非聚合索引、覆盖索引等话题。

一、数据结构及算法理论

Innodb存储引擎实现索引数据结构的是B+树，下面介绍几个数据结构。一步一步地说明为什么应该使用B+树。

1.1 B+树索引

B+树索引的结构与二叉树很类似。键值快速找到数据。但是，B+树种的B不是二叉，它表示平衡。注意：只有索引行。数据库通过将页面加载到存储器中来检索存储器中的数据，最后检索数据。

介绍二分搜索法。按排序（递增或减少）的顺序记录，在搜索过程中通过跳转查找。例如，示出了5、10、19、21、31、37、42、48、50、52的10个数量。

可以以三次搜索速度找到48。逐次搜索需要8次。对于上述10个数，依次检索的平均检索次数是5.5次，二分检索法是2.9次，最坏的情况是按顺序检索的次数是10次，二分检索的次数是4次。两点搜索将innodb页面Directory的插槽按主关键字的顺序保存，对于每个具体记录的查询将页面Directory分成两部分进行检索。

1.2 二叉查找树

数字表示各节点的键的值。在树里找。左子树的键值总是小于跟的键值，右子树的键值总是大于跟的键值。通过中序遍历得到键值：2、3、5、6、7、8。

查找树的平均查找次数为2.3次，但是查找树是可以任意构建。和这样调查顺序是一样的。因此，引用了取得二叉树平衡的想法，AVL树。

1.3 定义

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

二叉树的平衡非常快，但是为了维持二叉树的平衡，通常需要一次以上的左转和右转插入或更新后树木的平衡。

1.4 B+树特性

全部记录在叶节点中，按顺序保存，各叶节点（以页为单位）在逻辑上连续保存，是双向循环链表。

B+树插入必须确认插入后的叶节点中的记录还被排序，因此在插入时必须考虑以下三种情况。

数据库中的一个特征是B。因此，在数据库中，B+树的高度通常在2～3层，也就是说，正在寻找某个键行的记录。最多可以进行2～3次IO。普通盘每秒至少可以进行100次IO。

二、索引摘要和非编译索引

集合索引和非集合索引的区别在于页节点是否保存整个行的记录。

2.1 聚集索引

InnoDB存储引擎表是索引组织表，表格数据按主关键字顺序保存。集合索引是从各表的主键制作B+树，在叶节点中存储有表整体的行记录数据，因此索引聚集的叶节点也成为数据页。此特性用于收集索引，索引表中的数据也被确定为索引的一部分。同时B+树的数据结构相同。每个数据页面通过双向链接链接链接。

实际数据只由一个B+树排列。因此，每个表格只有一个链接索引。在许多情况下，查询优化器倾向于采用集中索引，因为它可以在索引的叶节点处直接找到数据。此外，由于定义了数据的逻辑顺序，所以可以快速访问对象范围的查询。查询优化器可以很快地发现需要扫描某范围的数据。注意各页的记录也用双向链保持。

2.2 非聚集索引

也叫辅助索引。数据行中没有全部数据。页面节点除了关键字之外，每个页面级别的索引都包含书签。InnoDB记忆引擎告诉我们索引对应的行数据在哪里。因为InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引书签是该行的数据的集合索引键。图是索引和辅助索引的关系。

用辅助索引检索数据时，InnoDB存储引擎创建循环辅助索引，用叶电平指针取得箭头键索引的键，用主键索引找到完整的行记录。例如，要在三个高度的辅助索引树中查找数据，必须找到辅助索引的主关键字。期间是3次。如果索引树的高度为3，则会检索3次组合索引。要搜索有完整行数据的页面，6次逻辑Io必须访问最终数据页面。