索引结构

MySQL 的索引是在存储引擎层实现的，不同的存储引擎有不同的结构。

一、索引结构分类

索引结构	描述
B+Tree 索引	最常见的索引类型，大部分引擎都支持 B+ 树索引
Hash 索引	底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询
R-tree（空间索引）	空间索引是 MyISAM 引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少
Full-text（全文索引）	是一种通过建立倒排索引快速匹配文档的方式，类似于 Lucene、Solr、ES

各存储引擎的支持情况

索引	InnoDB	MyISAM	Memory
B+tree 索引	支持	支持	支持
Hash 索引	不支持	不支持	支持
R-tree 索引	不支持	支持	不支持
Full-text	5.6 版本之后支持	支持	不支持

我们平常所说的索引，如果没有特别指明，都是指 B+ 树结构组织的索引。

结构	问题 / 特点
二叉树	顺序插入时会形成一个链表，查询性能大大降低；大数据量情况下层级较深，检索速度慢
红黑树	大数据量情况下层级较深，检索速度慢
B-Tree（多路平衡查找树）	以最大度数（max-degree）为 5（5 阶）为例：每个节点最多存储 4 个 key、5 个指针；叶子与非叶子节点都存数据
B+Tree	① 所有的数据都会出现在叶子节点；② 叶子节点形成一个单向链表（非叶子节点只做索引）

MySQL 对 B+Tree 的优化：在经典 B+Tree 的基础上，增加一个指向相邻叶子节点的链表指针，形成带有顺序指针的 B+Tree，提高区间访问的性能。

特点

原理：采用一定的 hash 算法将键值换算成新的 hash 值，映射到对应的槽位上，然后存储在 hash 表中。如果两个（或多个）键值映射到同一个槽位上，就产生了 hash 冲突（hash 碰撞），可以通过链表来解决。

存储引擎支持：MySQL 中支持 hash 索引的是 Memory 引擎；InnoDB 具有自适应 hash 功能，hash 索引是存储引擎根据 B+Tree 索引在指定条件下自动构建的。

相对于二叉树，层级更少，搜索效率高；
相对于 B-Tree：无论叶子节点还是非叶子节点都会保存数据，导致一页中存储的键值减少，指针也跟着减少，要同样保存大量数据只能增加树的高度，导致性能降低；
相对于 Hash 索引：B+Tree 支持范围匹配及排序操作。

InnoDB 主键索引的 B+Tree 高度

假设：一行数据大小为 1K，一页中可以存储 16 行数据；指针占 6 个字节，主键为 bigint 占 8 字节。

树高	估算
高度为 2	`n8 + (n+1)6 = 161024` → n ≈ 1170，约 `1171 16 ≈ 18736` 行
高度为 3	`1171 * 1171 * 16 ≈ 21939856` 行（约 2000 万）