乐趣区

一文系列一文掌握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 进行比较大小,而且增大了页分裂的概率
退出移动版