InnoDB存储引擎索引与算法

5.1. InnoDB存储引擎索引概述

InnoDB支持以下集中常见的索引：

• B+树索引
• 全文索引
• 哈希索引

前面提到过，哈希索引是InnoDB为了优化B+树索引而自动生成的自适应哈希索引，所以无法做到人为干预。

B+树索引就是传统意义上的索引，但是需要明确一点，B+树无法找到具体某一行记录，它只能找到记录所在的页，然后把页载入到内存，再进行查找。

5.2. 数据结构与算法

5.2.1. 二分查找法

不说了，数据结构基础

5.2.2. 二叉查找树和平衡二叉树

也不说了，不是本节重点。

5.3. B+树

在B+树中，所有记录节点都是按照键值顺序存放在同一层的叶子结点上。各节点之间通过双向链表链接，节点内就是多个页，页与页之间也是通过双向链表链接的。

5.4. B+树索引

B+索引在数据库中有一个特点就是高扇出性。聚族索引和辅助索引的区别在于，聚族索引存放的是是实际的数据，而辅助索引存放的是聚族索引的键(或者说表的主键)。

5.4.1. 聚集索引(又名：聚族索引/聚簇索引/主键索引)

聚集索引就是按照每张表的主键生成一棵B+树，同时叶子结点存放的是行记录数据，因此也将聚集索引的叶子结点称为数据页。

由于实际上数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。一般来说，优化器倾向于使用聚集索引，因为它能在B+树的叶子结点上直接获得数据。

聚集索引的另一个优点是，对于主键的排序查找和范围查找非常快。另外，因为B+树索引基于双链表，所以可以快速找到最后一个数据页，此时插入操作会很快。

另一个优势是范围查询，因为B+树的性质，所以可以很容易得到某一范围所在的页，然后完成读取即可。

5.4.2. 辅助索引

辅助索引的数据部分存放的是主键。每次通过辅助索引索引数据时，需要定位到主键，然后再通过主键索引定位到数据。

5.4.3. B+树索引的分裂

5.4.4. B+树索引的管理

可以通过ALTER TABLE或CREATE/DROP INDEX来创建或删除索引，同时用户可以设置对整个列的索引，也可以只设置某个列的开头部分数据作为索引。

5.5. Cardinality值