Mysql的InnoDB引擎的数据结构(B+树）以及聚簇索引的介绍

前言：自己的对知识的复习和归纳，参考网上资料和书籍（Mysql高性能），部分概念便于理解会做简单处理。

数据库中使用什么数据结构作为索引呢？

数据库的需求？

比较常见的查找需求：

假设是树结构呢，有什么问题？

我们来看下最简单的二叉树（以下提到的二叉树都指平衡二叉树）

那如果采用最简单的二叉树（平衡二叉树）作为数据库的索引存储，有什么问题呢？

首先，索引是存储存在在硬盘的。
(比如：给某张表，1亿的数据记录建立二叉查找树索引，索引中大概会有一亿的节点，假设每个节点占用16字节，大约需要1GB)

1.不支持区间查找 — > 非叶子节点不存储数据，只做索引（叶子节点的索引），然后把叶子节点连接起来，就可以支持区间查找。
2.速度慢（把数据存储在硬盘，每个节点的读取或者访问，都对应一次磁盘IO操作(ms级别)，数的高度就对应每次查询的IO次数。） — > 降低树的高度，M叉树。

如果M位100, 100叉树，一亿的索引节点，树的高度为3，所以最多3次磁盘IO操作就能获取到数据。
所以，索引的查找从磁盘IO读取变成内存查找。

这就是B+树(有序数组链表+平衡多叉树)

什么是B树(多路平衡查找树)：

只是一个每个节点的子节点个数不能小于 m/2 的m叉树 –> 有序数组 + 平衡多叉树

B+树、磁盘 == 非常快的查找速度(索引)：

程序的访问局部性：当一个数据被用到时，其附近的数据也通常会马上被使用。
- 时间局部性：被使用的数据，未来很大概率会被再次使用。
- 空间局部性: 被使用的数据，其附近的数据，大概率会被使用。
磁盘的预读取：磁盘是按页（简单理解为4KB）读取。 — > 如果是B+树，让一个节点的大小 == 一个磁盘页，一次磁盘IO读取就是一个节点，而B+树中，一个节点内的数据是连续的，所以能充分利用程序的访问局部性原理。（索引可以将随机I/O变为顺序I/O。）

比较：二叉树 — >如果索引数据大，树高度深，相邻数据的节点在物理位置距离远，每次预读取的数据基本基本不会被用到。

那我们来看下磁盘是怎么读取数据的？

先看下磁盘结构：

磁盘的读写：读写主要是通过传动手臂上的读写磁头来完成。实际运行时，主轴让磁盘盘片转动，然后传动手臂可伸展让读写磁头在盘片上进行读写操作。

扩展：磁盘顺序读取的效率很高。合理利用，顺序读取的速度甚至比内存高（kafka、rocketMq等中间件，就是利用磁盘的顺序读取，来实现高性能）。

聚簇索引和非聚簇索引

聚簇索引和非聚簇索引概念

聚簇的意思：数据行被按照一定顺序一个个紧密地排列在一起存储。（索引是有序的）
InnoDB : 主键索引和数据文件简单理解为同一份文件

从MYISAM存储的物理文件我们能看出，MYISAM引擎的索引文件（.MYI）和数据文件(.MYD)是相互独立的。

聚簇索引的优点和缺点

优点
- 1.查询通过聚簇索引可以直接获取数据，相比非聚簇索引需要第二次查询（非覆盖索引的情况下）效率要高。
- 2.聚簇索引对于范围查询的效率很高，因为其数据是按照大小排列的。（磁盘顺序读取）
缺点
- 1.索引的更新代价高：数据更新，为了保持聚簇索引的有序，需要将数据移动到相应的位置，而且可能导致页分裂（页已满）。
- 2.插入的速度严重依赖插入的顺序，如果是按照主键索引的速度插入，非常快，非主键索引的插入，慢。
- 3.二级索引访问需要两次索引查找，而不是一次。
- 4.聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。（未get到）

扩展：

InnoDB的插入：
首先，操作系统写磁盘是定期flush将缓存刷到磁盘。

多条记录如果是按照主键索引的顺序插入：