索引的数据结构

用户6256742

发布于 2024-07-11 10:01:02

670

发布于 2024-07-11 10:01:02

文章被收录于专栏：网络日志

目录结构

废话少说，不巴巴，直接上正文。

什么是索引

可以简单理解为索引好比一本书的目录，通过目录我们可以快速定位到我们要查看的章节。

MySQL 中的数据同样也是根据索引分类，通过索引可以快速高效的查询到我们想要的数据。

索引的优缺点

MySQL 官方对索引的定义：索引（Index）可以帮助 MySQL 高效获取数据的数据结构。

索引的本质：索引是一种数据结构。可以简单理解为索引是一组满足某种特定算法，排好序的快速查找的数据结构，这种数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查找算法。

InnoDB 存储引擎底层默认采用 B+Tree 作为索引的数据结构

先看下二叉搜索树的结构（一个节点存放一条数据）：

可以理解为 B+Tree 是从二叉搜索树的基础上演变而来的（一个节点存放多条数据）。

建立索引的目的是为了减少磁盘的 I/O 次数，加快查询效率。

索引是在存储引擎中实现的，不同的存储引擎支持的索引类型不一定相同。

存储引擎可以定义每张表的最大索引数和最大索引长度。所有的存储引擎支持每个表至少 16 个索引，一个索引的长度为 16 个字节，所以支持的最少总索引长度为 256 个字节。

优点

提高数据检索效率，降低数据库磁盘 I/O 成本
通过创建唯一索引，可以保证数据库中每一行的数据的唯一性
加速表和表之间的连接，对于有依赖关系的子表和主表联合查询的时候，可以提高查询速度
在使用分组和排序进行数据查询时，可以显著减少查询中分组和排序的时间，大大降低了 CPU 的消耗

缺点

增加索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间会越来越大
除了数据表要占用空间之外，索引也需要占用磁盘空间，并且不同的存储引擎，索引和数据的存储位置可能不同，InnoDB 存储引擎是将索引和数据存放在一个以.ibd结尾的文件中，MyISAM 存储引擎将索引和数据分开存储，索引存放在以.myi为结尾的文件中，数据存放在以.myd结尾的文件中
虽然索引大大提高了查询速度，但是却会降低更新表的速度。当表中的数据要进行增删改的时候，索引也要动态维护（要重新动态分组归类排序数据的存储结构），这样就降低了数据的维护速度。

InnoDB 数据存储格式

区分记录

用户记录页和 目录项记录页如何区分？

使用记录头里的record_type属性，各个取值的含义如下：

0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录

假设有一张数据表 test_table有四个字段：c1、c2、c3

create table test_table (
  c1 int,
  c2 int,
  c3 char,
  PRIMARY KEY(c1)
) engine=InnoDB

由于页的编号可能不是物理连续的，只要求再逻辑上连续即可，向表中插入多条数据后，可能如下图所示：

但是挨个查找的话，数据量大的时候比较耗时。

为每个页建立一个目录项，每个目录项有一个 key（存储当前页最小的主键值）、page_no 存储页码，大致结构如下如下图所示：

行和行之间以单链表存储，页和页之间以双向链表存储。

记录与记录之间以单链表存储，叶子节点与叶子节点之间以双向链表存储。

迭代优化 1：目录项记录的页

为每个页新建一个目录项之后，考虑到后续数据量会越来越大，如果目录项在物理空间中连续存储，对于新增页或删除页时，目录项也会随之发生，这样就会消耗大量的时间，所以将目录项也简单理解为一个行记录，目录项之间也用单项列表形式存储，也就是为多个目录项建立一个页，这样新增或者删除时，直接改变指针指向即可，效率客观的很，如下图所示：

迭代优化 2：多个目录项记录的页

多个目录项记录页之间的关联如下图所示：

迭代优化 3：多个目录项记录页记录的页

多个目录项记录页组成的也目录页，如下图所示

B+Tree 结构

层层往上汇聚之后，最终形成了一个 B+Tree 的结构：

不论是存放用户记录的数据页，还是存放 目录项记录的数据页，最终都存放在 B+Tree 的结构中，所以我们撑这些数据页为节点。

实际用户记录都存放最下面的节点上，这些节点称为 叶子结点，其余用来存储 目录项的节点被称为 非叶子节点或 内节点，其中 B+Tree 最上边的节点也称为 根节点(可能会有多个根节点)。

一个 B+Tree 的结构可以分为很多层，规定最下面的层，也就是存放实际用户记录的那一层为第 0层，之后依次往上加。

上述的例子中我们假设存放实际记录的页 最多存 3 条记录，存放目录项记录的页 最多存放 4 条记录，其实真实的开发环境中存放的记录数非常大，假设存放实际记录的数据页（最下层的叶子节点）最多可以存放 100 条记录，存放目录项的数据页（上层的非叶子节点）最多可以存放 1000 调记录，那么计算方式如下：

如果 B+Tree 有 1 层，也就是只有一个存放用户记录的节点，最多能存放 100 条记录
如果 B+Tree 有 2 层，最多能存放 1000 * 100 = 10,0000条记录
如果 B+Tree 有 3 层，最多能存放 1000 * 1000 * 100 = 1,0000,0000条记录
如果 B+Tree 有 4 层，最多能存放 1000 * 1000 * 1000 * 100 = 1000,0000,0000条记录

到达 4 层的时候，就可以存放 1000,0000,00001000 亿条记录了，但是真实的环境中几乎不可能存到 1000 亿条，所以我们用到的 B+Tree 一般都不会超过 4 层。

假设我们是精确查找某一行数据，那在每一层通过二分法或者其他算法找到目录数据页，一次 I/O，然后再查找第二层的数据页，也是一次 I/O，所以精确查找某一行数据最多会经历四次 I/O，如果是范围查询就会有很多次 I/O 了。

常见索引概念

聚簇索引

一个表中只能有一个聚簇索引，主键就是一个默认的聚簇索引。

聚簇索引的叶子节点（最下层的节点），存储的是一整行记录

聚簇索引的叶子节点（最下层的节点），存储的是 **一整行记录** 。

二级索引

二级索引也称为非聚簇索引、辅助索引等，它是主键索引之外的索引。

我们可以为非主键列各自建立一个非聚簇索引（B+Tree），不同的 B+Tree 树的数据采用不同的排序规则，

假设我们为 c2列创建一个非聚簇索引，B+Tree 的结构大致如下：

上述 B+Tree 结构的叶子节点中的数据分布：

蓝色方块 存储的是 c2 列本身的 value
黄色方块 存储的是 c1 列（主键）的 value

重点：

非聚簇索引中的叶子节点中，存储的是 当前列的值 和 主键值 。

假设有一个表 test_table 有三个字段 c1、c2、c3

如果我们有一条查询 SQL：

select c1, c2 from test_table where c2 = 4

c2 列是非聚簇索引，索引查找顺序为下图所示：

因为此时的叶子节点中包含了我们要查找的 c1 和 c2，所以直接将记录返回给客户端。

如果查询 SQL 为如下格式：

select c1, c2, c3 from test_table where c2 = 4
或
select * from test_table where c2 = 4

查询结果中 包含了非索引列，索引查找顺序为下图所示：

第一步： 要先走一遍上述的流程，根据 where 条件定位到 c2 列索引数据，此时有两条记录满足条件
第二步： 然后根据主键（黄色方块的值 c1=4、c1=10），通过主键索引（聚簇索引）的结构再查询一次

这个第二步的过程我们称之为：回表查询。

回表查询

回表查询也是面试常考点，因为回表查询会降低查询效率，增加了数据库的 I/O 次数，所以为了提高查询效率我们应该尽量降低回表查询的次数。

非主键列建立的 B+Tree 需要一此回表查询才可以定位到完整的用户记录，所以称这种索引为 二级索引（second index）或 辅助索引。

那为什么我们不把一整行记录数据放在非聚簇索引的叶子节点上呢？

原因：一个表中可以有多个非聚簇索引，那如果每个非聚簇索引的叶子节点上都存放一份完整的数据，假设表中有 1000 行数据，总共四个字段，每个字段单独建一个索引，那最终就会存储四份数据（4 个 1000 行），这样会造成大量数据冗余，浪费存储空间。

非聚簇索引的存在不影响聚簇索引的组织结构，所以一张表可以有多个非聚簇索引。

总结：

聚簇索引的叶子节点存储的是 用户记录，非聚簇索引的叶子节点存储的是 数据位置(索引列的值和主键值)。
一个表中只能有一个 聚簇索引，但是可以有多个 非聚簇索引。
使用聚簇索引的时候，数据的 查询效率很高，但是对表进行增删改操作的时候，效率会比非聚簇索引要低的多。

对表进行新增和删除操作，对索引的影响很大，特别是主键索引，二级索引影响相对较小。

对标进行更新操作，对主键索引有影响，如果更新的字段中也存在索引，只会对涉及到的二级索引有影响。

联合索引

联合索引：多个非主键列构成的索引。

下图 B+Tree 为一个联合索引结构（idx_c2_c3），其叶子节点中存储的数据如下：

蓝色方块为 c2 字段值
紫色方块为 c3 字段值
黄色方块为 c1 字段值（主键）

假如有一个查询 SQL：

select c1, c2, c3 from test_table where c2 = 4 and c3 = 'u'

执行过程如下：

细心的伙计可能看到了在页 50 中存在一条记录：

4	a	4

那为啥查找链路没走到这呢？原因在页 59 中，

2	e	50
4	o	55

因为联合索引是多个字段进行排序后的数据结构，也就是说要先以 c2 字段排序，然后再以 c3 字段排序。

联合字段索引在 where 条件中虽然是精确查询：where c2 = 4 and c3 = 'u'

但是在非叶子节点中是以范围查找的，可以理解为：where c2 >= 4 and c3 >= 'u'，到了叶子节点才会精确判断：where c2 = 4 and c3 = 'u'

所以判断了 c2 >= 4之后，满足条件的有这两行 目录项记录，然后再根据 c3 >= 'u'判断，因为 u > e、u > o、o > e，所以最终满足条件的是：4 o 55这条目录项记录，最终查询链路也是会从这条路径走下去。

InnoDB 的 B+Tree 索引的注意事项

根页面位置万年不变

上述我们在索引迭代的过程中，为了更佳形象的描述，所以将顺序暂且定位自下而上，往上汇总目录项页。

但实际上 B+Tree 的形成是自上而下的，大致过程如下：

每当为某张表创建一个 B+Tree 索引（聚簇索引不是人为创建的，创建表的时候默认创建），都会为这个索引创建一个 根节点页面。最开始表中没有数据的时候，每个 B+Tree 根节点中既没有用户记录，也没有目录项记录。
随后向表中插入记录时，先把用户记录存储到这个 根节点中。
当根节点中的 可用空间用完时，继续插入记录，此时存储引擎会将根节点中的所有记录复制一份到另一个新分配的页中，比如 页 a，然后对这个新页进行 页分裂的操作，得到另一个新的页，比如 页 b。这时候根据插入记录的键值（聚簇索引的话根据主键值，二级索引的话根据索引列值、主键值）的大小就会被分配到 页 a或者 页 b中，而根节点就升级为存储目录项的页。

特别注意：

一个 B+Tree 索引创建之后，它的根节点便不会再移动。

也就是对某个表创建索引之后，它的根节点的页号就会被存储在某个地方，然后凡是 **InnoDB 存储引擎**需要用到这个索引的时候，就会从那个固定的地方取出对应根节点的页号，从而来访问这个索引。

内节点中目录项记录的唯一性

我们知道 B+Tree 聚簇索引 的内节点中目录项记录的内容是 索引列 + 页号的组合，但是这个组合对于 非聚簇索引就不太适用，拿 test_table表举例，总共有三个字段：c1（主键）、c2、c3，假设这个表中有如下几行数据：

c1	c2	c3
1	1	'u'
3	1	'd'
5	1	'y'
7	1	'a'

当我们为 c2 列创建二级索引时，如果目录项页中的记录只是 索引列 + 页号的组合时，那么 c2列建立索引之后，B+Tree 的结构大致如下图所示：

B+Tree 数据结构组成如下：

黄色方块为索引列的值
蓝色方块为主键值
红色方块为页码值

通过上图二级索引数据结构，我们可以看到页 3 作为一个目录项记录页，当二级索引列存在多个相同值的记录时，非叶子节点中的目录项只存储索引列 + 页号时，我们无法区分应该去哪个数据页查询数据，或者说当新增数据时：(9、1、'u')，对应表中的字段顺序为：c1、c2、c3，此时插入的 c2 列的值也为 1，在上述页 3 中存储的两条目录项记录的索引值都为 1，所有无法区分到底该插入哪个记录对应的页中。

为了解决问题，也就是说无论是实际记录还是目录项记录，都要实现唯一性，此时我们就可以把 主键值和索引列值一起存储在目录项记录中，如下图所示：

插入数据：(9、1、'u') 的执行过程应该如下图所示：

一个页面中至少存储两个记录

一个 B+Tree 只需要很少的层级就可以轻松存储数亿条记录，查询速度也是相当不错。

B+Tree 本质上就是一个大的多层级目录，每经过一个目录时就会过滤掉很多无效的子目录，最终会查找到存储真实数据的目录。

如果说一个大的目录中只存放一个子目录是啥效果？也就是会有很多层目录，并且我们从根节点开始查找，经过很多层目录之后，最后找到了一个目录，里面只存储了一条数据，你说气人不，费老大劲，经历了那么多次数据库 I/O，就查到一条数据，效率贼低。

所以说 InnoDB 存储引擎中的一个数据页至少存储两条记录。

MyISAM 索引方案

MyISAM 索引的原理

MySQL 官方一般统称 B-Tree 为 B+树，适用于 B-Tree 的存储引擎如下表所示：

索引/存储引擎	MyISAM	InnoDB	Memory
B-Tree 索引	支持	支持	支持

虽然多个存储引擎都支持 B-Tree 索引，但是在底层的实现原理上却是不同的。

InnoDB 和 MyISAM 的底层默认使用 B-Tree 索引，而 Memory 底层默认使用 hash 索引。

InnoDB 的索引即数据:

在聚簇索引的叶子节点中存储的是完整的数据：主键 + 数据
在非聚簇索引的叶子节点中存储的数据是：索引列 + 主键

MyISAM 的索引虽然也是 B-Tree 结构，但是底层确实将 数据和索引分开单独存储

数据文件(.myd 文件)：存数据的文件，插入记录时，并没有按照主键大小刻意去排序，有多少塞多少
索引文件(.myi 文件)：MyISAM 为每张表的主键都创建一个 B-Tree 索引，但是叶子节点中存储的数据是：主键 + 地址

大致结构如下图所示：

索引组成结构：

绿色方块为 主键值
紫色方块为 地址偏移量

有一定我们要清楚，因为主键索引每一行记录都是唯一的，所以只需要存储 主键+地址即可，但是非主键列（二级索引）是不唯一的，很可能会重复，如果为非主键列创建索引，大致如下图所示：

这里康师傅应该是漏掉了二级索引数据重复的举例图，所以应该再加一个主键值，最终组成节点的机构为：

叶子节点：索引列 + 主键 + 地址
非叶子节点：索引列 + 主键 + 页码

MyISAM 和 InnoDB 的对比

MyISAM 中的索引都是 非聚簇索引，InnoDB 中包含两种索引 聚簇索引和 非聚簇索引
MyISAM 的叶子节点中存储的为 索引 + 地址，所以查询到地址之后，至少还需要一次回表查询；InnoDB 的聚簇索引叶子节点中的存储的是 完整的记录，所以根据主键查询可以直接返回，不需要回表查询
MyISAM 索引记录存储的是 地址，InnoDB 聚簇索引存储的是 主键 + 数据，非聚簇索引 data 域存储的是 主键
MyIASM 回表查询的速度 非常快，因为叶子节点中查询到是数据的地址偏移量直接去文件中查找相当的快，而 InnoDB 叶子节点查到的是主键值，根据主键再去聚簇索引中查询数据，虽然也不慢，但是相比于用地址查询，还是差了点
MyISAM 可以没有主键；InnoDB 必须要有主键，如果没有显示指定，则 MySQL 自动选择一个 非空且能唯一标识记录的列作为主键，如果不存在这样的列，则会自动为 InnoDB 表生成一个 隐含字段 作为主键，字段长度为 6 个字节，类型为长整型。

索引的建议

为什么不建议使用过长的字段作为主键？

因为二级索引节点中都会引用主键索引，过长的主键索引会导致二级索引树结构变的很臃肿
用非单调的字段作为主键在 InnoDB 中不是一个好主意，已因为 InnoDB 索引本身是一颗 B+Tree，非单调的主键会导致在插入记录时，数据文件为了维护树的结构而频繁的进行 页分裂，导致性能比较低效，而使用 自增且单一的字段作为主键是个好的选择

InnoDB 和 MyISAM 索引分布对比如下图所示：

索引的代价

索引虽好，但不能乱建（劲酒虽好，但不能贪杯哦）：

占用空间：每个索引都要建立一棵 B+Tree，每个节点都是一个数据页，一个数据页为 16KB，一棵很大的 B+Tree 由很多个数据页组成，就会占用很大的空间
消耗时间：对表进行 增删改操作时，都要去修改各个 B+Tree 的结构。因为 B+Tree 的 各个节点 都是根据索引列值 从小到达按顺序存储的而存储的 双向链表。而不论是叶子节点还是内节点（非叶子节点）中的记录都是按照索引列的值从小到达按顺序存储的而存储的 单向链表，所以如果对表记性 增删改的操作，会对各个节点和记录的排序造成破坏，存储引擎为了维护索引结构的平衡会进行额外的 记录移位、页面分裂、页面回收等操作，会造成性能大幅下降。

一个表中创建的索引越多，占用的空间越大。在增删改操作时，存储引擎维护索引消耗的时间就越多。

为了能建立好的索引，所以要根据数据的分布情况建立合理的索引结构。

MySQL 数据结构选择的合理性

B+Tree 中的根节点从创建开始是常驻内存中的，每次查询数据的时候，从内存中的根节点查找到合适的子节点记录（这一步是不需要磁盘 I/O 的），所有剩下最多三层节点，所以查询某一个键值的时候，最多只需要 1~3此磁盘 I/O。

全表扫描

全表扫描也就是使用的非主键列（且没有建立索引）作为 where 查询条件，只能进行全表扫描，性能非常差。

常见的加速查找速度的数据结构，常见的有两类：

树：例如平衡二叉树，增删改查的平均时间复杂度都是 O(log2N)
哈希：利润 HashMap，增删改查的平均时间复杂度都是 O(1)

Hash 结构

Hash 本身是一个函数，也被称为散列函数，可以帮助我们大幅度提升检索数据的效率。

Hash 是通过某种特定的算法（MD5、Base64、SHA256 等）将输入转化为输出。

相同的输入永远可以得到相同的输出。

采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+Tree 需要自顶向下一次查找，多次访问节点才能找到数据，中间需要多次 I/O 操作，从效率上来说 Hash 比 B+Tree 更快。

Java 中常用的 HashMap 和 HashSet 的底层就是用的哈希结构存储的数据。

在 Hash 的方式下，一个元素处于 h(k)中，即利用哈希函数算法，根据关键字 k 计算出一个哈希值（也就是在槽中的位置），函数 h 将关键字域映射到哈希表 T[0……m-1] 槽位上。

上图中哈希函数 h 有可能将两个不同的关键字映射到同一个位置，这叫作 哈希碰撞，在数据库中一般采用 链接法来解决，也就是将散列到同一个槽位上的元素放到一个链表中，如下图所示：

既然 Hash 结构效率高，那为什么 MySQL 索引结构要设计成树形结构呢？

Hash 索引仅能满足(=)、(<>)、(IN)等条件查询，如果进行 范围查询，哈希型的索引时间复杂度会退化为 O(n)；而树形的有序性依然可以保持 O(log2n) 的高效率。
Hash 索引还有一个缺陷，数据的存储是 无序的，在 order by 的情况下，使用 Hash 索引还需要对数据重新排序
对于联合索引的情况，Hash 值是将联合索引键合并之后一起来计算的，无法对单独的一个索引键或者多个索引键进行查询
对于等值查询，通常 Hash 索引的效率很高。但是也有一种特殊的情况，就是 索引列的重复值有很多，效率就会很低下，这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到要查询的关键字，非常耗时，所以 Hash 索引一般不会用在重复值很多的列上，比如性别、年龄字段等。

Hash 索引适用存储引擎如下所示：

Hash 索引的适用性：

Hash 索引存在很多限制，相比之下 B+Tree 索引的适用会更加广泛，不过有些场景使用 Hash 索引会更加高效，比如在键值对数据库中，Redis 底层存储的核心就是 Hash 表。

另外，InnoDB 本身不支持 Hash 索引，但是提供了 自适应 Hash 索引（Adaptive Hash Index）。

什么情况下才会使用自适应索引呢？

如果某个数据经常被查询到，当满足一定条件时，就会将这个数据页的地址存储到 Hash 表中，这样下次查询的时候就可以直接到这个页面所在的位置，这样 B+Tree 也相当于具备了 Hash 索引的优点。

上图结构：

左边是自适应 Hash 索引之后的查询过程
右边是正常通过根节点查询叶子节点的过程

采用 Hash 索引目的是为了方便根据 SQL 的查询条件定位到叶子节点上，特别是 B+Tree 比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。

通过命令查看是否开启了自适应哈希索引：

show variables like '%adaptive_hash_index%'

二叉搜索树

二叉搜索树的特点：

每个节点只能有两个子节点
左子节点 < 当前节点，右子节点 >= 当前节点

查询规则：

最基础的二叉搜索树，搜索某个节点和插入节点的规则一样，假设要搜索的的数值为 key：

如果 key 大于根节点，则在右子节点中进行查找
如果 key 小于根节点，则在左子节点中进行查找
如果 key 等于根节点，那当前根节点就是要找的数据

特殊情况，如果给出的数据如下所示：

树结构偏了，这也不算很极端的情况，真实的数据很有可能这样存储，但是这样的二叉搜索树，在查询性能上就退化为了一条链表，时间复杂度也编程了 O(n)，上面第一棵树的深度为 3（最多查询 3 次），第二棵树的深度是 7（最多查询 7 次），那如果树的深度更深，几十层、甚至成百上千层深，查询比对一次就是一次 I/O，那查询效率就会非常低下。

我们可以看出上面的树都有一个特点，就是 高瘦，每个节点最多只能有两个子节点，如果想提高查询效率，降低 I/O 次数，就要想办法减少树的深度，也就是要从 高瘦变为 矮胖。

AVL 树

为了解决上述二叉查找树退化为链表的问题，又提出了 平衡二叉搜索树，又被称为 AVL 树，它在二叉搜索树上增加了约束。

特点： 它是一棵空树或左右两棵子数的高度差最大不会超过 1，并且两边的子树都是二叉平衡树。

如果树结构偏了，则让节点自动平衡旋正，如下图所示：

上面有 5 个层级，如果要查找的数据恰巧在第 5 层叶子节点中，需要经历 5 次 I/O 操作，虽然效率比上面的二叉平衡搜索树高了很多，但是如果数据量非常大，树的层级还是很多，I/O 次数依然会很多，效率也会很低。

这对这种情况，我们把 二叉树 改为了 M 叉树（M>2），也就是说打破上面每个节点只有两个子节点的问题，如果 M=3，同样存储上述 31 个节点，结构如下：

每个节点都有 3 个子节点，整体变为了最多 4 次 I/O 操作。

这样看来，相比最开始的 高瘦，确实 矮胖了很多。

结论：M（M>2）叉树的高度远小于二叉树的高度。

B-Tree

B 树（Balance Tree），也称为 多路平衡查找树，简写为 B-Tree（中间的杠，是为了将其连起来，不是减号）。

它的高度远小于二叉平衡树。

B-Tree 的结构如下图所示：

B-Tree 作为多路平衡二叉树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。

阶是每个磁盘最多容纳的关键字个数。

每个磁盘块中，包括了 关键字和 子节点的指针。

一个磁盘中包含 x 个关键字，那么指针数就是 x+1。

如果一个 B 树的阶是 100，树的层级为 3，那最多可以存储 100 万条数据。对于大量的索引数据，采用 B-Tree 的结构是非常合适的。

结论：

B-Tree 相比于平衡二叉树来说磁盘 I/O 操作要少很多，查询效率也就越高。
只要树的高度足够低，I/O 次数足够少，查询效率就会越高。
B-Tree 在增删改的时候会导致树不平衡，这个时候就需要树进行自旋保持树的自平衡。
关键字结合分布在整棵树中，也就是叶子节点和非叶子节点都会存储数据。
其搜索性能等价于在关键字集合内做一次二分查找。

真正 B-Tree 的结构如下：

B+Tree

B+Tree 也是一种多路搜索树，在 B-Tree 的基础上改进。

主流的 DBMS 都支持 B+Tree 的索引方式，相比于 B-Tree，B+Tree 更适合于文件索引系统。

B-Tree 和 B+Tree 的区别：

B-Tree 的每一个节点都存储数据， B+Tree 的中间节点不存储数据
B-Tree 查询不稳定，B+Tree 查询相对较稳定
B-Tree 查询效率较低，B+Tree 查询效率较高，以为捏 B+Tree 更矮胖（阶数更大，层数越少，I/O 次数越少）
在查询范围上，B+Tree 的效率要更高
- B+Tree 的所有数据都在叶子节点上，并且数据是顺序排序的，可以通过指针查找
- B-Tree 的数据存储左右的节点上，需要通过中序遍历查找

B-Tree 和 B+Tree 都可以作为 MySQL 的所以结构，没有谁比谁更好，他们两个都有各自的应用场景，结合场景才能发挥各自的优势。

为了减少 I/O ，索引数会一次性加载到内存中吗？

索引都是存储在磁盘中的，如果数据量很大，那索引的大小也会很大，甚至几个 G。

所以不可能一次性加载到内存中，只能逐一加载每一个磁盘页，因为磁盘页对应着索引的节点。

B+Tree 的存储能力如何？为何说一般查找一个记录，最多只需要 1~3 次 I/O 操作？

首先我们清楚一个数据页的大小为 16KB，一般表的主键类型为 INT（4 个字节）或 BIGINT（8 个字节），指针类型一般也为 4 个字节或 8 个字节，也就是一个数据页大概存储 【16KB / (8B+8B) = 1k 个键值】 ，因为这是非叶子节点不存储数据，所以键值会多一点，但真实的数据表一般都会挺大的，叶子节点中的每个页可能大概会存储 500-1000 条，假设我们取每页 500 条数据，一个深度为 3 的 B=Tree，可以维护 1000 _ 1000 _ 500 = 5 亿条数据。

实际上每个数据页可能存不满，因此在数据库中，B+Tree 的高度一般在 2~4层左右。假设达到了 4 层，那顶层也就是根节点，根据存储引擎的设计，根节点一般从创建开始数据页地址就会存储在内存中的某个地方，也就是说这个数据页不用磁盘 I/O 已经在内存中了，所以剩下三层，最多进行三次 I/O 操作，所有说查询一条记录，最多只需要 1~3 次 I/O 操作。

Hash 索引和 B+Tree 索引的区别？