MySQL索引底层实现原理。

1.索引的本质

我们知道索引的作用是提升数据查询的速度，降低来IO操作，而快速检索的实现的本质是数据结构，因此索引的本质就是数据结构。

2.索引常见的数据结构

• Hash
• 二叉查找树(BST)
• 平衡二叉树(AVL)
• 红黑树
• B-Tree
• B+Tree

3.MySQL索引的底层实现

MySQL不论MYISAM还是INNODB都是使用B+Tree实现索引。

InnoDB存储引擎存储数据库数据，一共有两种文件，frm文件：表的结构。 ibd文件: 数据和索引存储文件。数据以主键进行聚集存储，把真正的数据保存到叶子节点中。

4.InnoDB索引实现详解

1).什么是b+树

B+树的特点如下：

• 每个父节点元素出现在子节点中，是子节点的最大或最小元素。
• 根节点的最大元素也是B+树中的最大元素
• 所有关键字都在叶子结点出现，包含了全量元素信息。
• 每个叶节点都带有指向下一个元素的指针，从而形成了一个有序链表。

下面就是用B+树实现的十二生肖的索引存储结构。

InnoDB表只有一个聚集索引，表数据文件本身就是按B+Tree组织的一个索引结构文件，聚集索引-叶子节点包含了完整的数据记录。

下面就是B+树实现存储一张关系型二维表示意。

2).B-树和B+树的区别

• B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
• B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B树每个节点 key 和 data 在一起，则无法区间查找。
• B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。