一文系列一文掌握mysql索引底层原理

1、铺垫：几种树的介绍

第一种：二叉查找树

不适合用作数据库索引：

(1)当数据量大的时候，树的高度会比较高，查询会比较慢 ；
(2) 每个节点只存储一个记录，可能导致一次查询有很多次磁盘 IO；

第二种：B 树

特点：

(1)不再是二叉查找，而是 m 叉 查找；
(2)叶子节点，非叶子节点，都存储数据 ；
(3) 中序遍历，可以获得所有节点；

B 树为何适合做索引？

(1)由于是 m 分叉 的，高度能够大大降低；
(2)每个节点可以存储 j 个记录，如果将节点大小设置为页大小，例如 4K，能够充分的利用预读的特性，极大减少磁盘 IO；

第三种：B+ 树

B+ 树仍是 m 叉搜索树，在 B 树的基础上，做了一些改进：

(1)非叶子节点不再存储数据，数据只存储在同一层的叶子节点上 ；
(2) 叶子之间，增加了链表，获取所有节点，不再需要中序遍历；

B+ 树比 B 树有更优的的特性：

(1)范围查找 ，定位 min 与 max 之后，中间叶子节点，就是结果集，不用中序回溯；
(2) 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量 磁盘存储 ；非叶子节点存储记录的 PK，用于查询加速，适合 内存存储 ；
(3) 非叶子节点，不存储实际记录，而只存储记录的 KEY 的话，那么在相同内存的情况下，B+ 树能够存储更多索引；

关于局部性原理

(1)磁盘预读 ：磁盘读写并 不是按需读取，而是按页预读 ，一次会读一页的数据，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘 IO，提高效率( 通常，一页数据是 4K)；
(2)局部性原理 ：软件设计要尽量遵循“数据读取集中”与“使用到一个数据， 大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘 IO；

2、聚簇索引和非聚簇索引

聚集索引

以 innodb 为例，在一个数据 table 中，它由 table.frm、table.idb 组成。table.frm 保存表结构的定义。table.idb 保存的是数据和索引。

在 innodb 中，既存储主键索引值，又存储行数据，称之为聚簇索引。

非叶子节点只记录 KEY，叶子节点存储实际记录行。

• 同一个表中，聚簇索引 只能有一个，因为 无法同时把数据行放在两个不同的地方

PRIMARY KEY 是一种典型的 聚簇索引 ，InnoDB 的 聚簇索引 具体选择策略如下：

• 默认 主键索引为聚簇索引 ，如果没有定义主键，会 选择一个唯一的非空索引 来代替，如果没有这样的索引,InnoDB 会 隐式定义个主键 来作为聚簇索引.

聚簇索引的优点

1. 数据访问更快。聚族索引将索引和数据保存在同一个 B -Tree 中，因此从聚族索引中获取数据通常比在非聚族索引中查找更快
2. 使用 覆盖索引 扫描的查询可以直接使用节点中的主键值

聚簇索引的缺点

1. 更新聚簇索引列的代价很高，因为会强制 InnoDB 将每个被更新的行 移动到新的位置
2. 二级索引的叶子节点存储的是主键的值，因此访问需要两次索引查找 ( 回表)，而不是一次。
3. 基于聚簇索引的表在 插入新行，或者主键被更新 导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次分裂操作。页分裂会导致表占用更多的磁盘空间。

非聚集索引

以 MyISAM 为例，在一个数据 table 中，它由 table.frm、table.MYI、table.MYD 组成。table.frm 保存表结构的定义。table.MYI 保存的是索引、table.MYD 保存的是数据 。在用到索引时， 先到 table.myi(索引树)中进行查找 ，取到数据所在 table.MYD 的行位置，拿到数据。所以 MyISAM 引擎的索引文件和数据文件是独立分开的，则称之为 非聚簇索引。

3、索引类型

主键索引

• 不可重复，不可为空
• mysql 必须有主键索引(即使不配置，也会默认有一个，用于构建 B + 树)

单列索引

使用字段关键字建立的索引，主要是提高查询速度

唯一索引

• 不可重复，可为空。
• NULL 表示的是未知，因此两个 NULL 比较的结果既不相等，也不相等，结果仍然是未知

组合索引

联合索引是指对表上的 多个列进行索引 。联合索引也是一颗 B + 树，不同的是联合索引的键值数量不是 1，而是大于等于 2。遵循 最左前缀匹配原则

全文索引

在 5.6 版本之前，只有 MyISAM 引擎支持全文索引，在 5.6 版本后 InnoDB 引擎也支持全文索引，在 mysql 中全文索引不支持中文。

4、拓展

mysql 页文件默认为 16K，将数据放在叶子节点，则非叶子节点可以存储更多的索引值

SHOW GLOBAL STATUS like 'Innodb_page_size';

假设每行数据为 1K，一页可以存放 16 条数据。

• 如果索引是 bigint 类型，占 8B，指针占 6B，一页可以存储 16384/(8+6) = 1170 个(主键 + 指针)
• 树高为 2 的话，可以保存 1170 * 16 = 18720 条行数据
• 树高为 3 的话，可以保存 1170 1170 16 = 21902400. 可以达到 千万级别

为什么 Innodb 表必须要有主键，并且推荐使用整型的自增主键？

• 没有定义主键也 会自动创建个主键(原因前面已经说了)
• 使用整型是为了节省空间，在 16K 的页容量里可以存储更多的值
• 使用自增主键是结合树的特性，减少页分裂出现的概率(其实如果使用自增 id 在插入新行，或者 id 被更新导致需要移动行的时候，也会页分裂，前面也有说到了)，如果使用的是 uuid 的话，每次插入都需要转 ASCII 进行比较大小，而且增大了页分裂的概率