目录

一、MySQL架构图

二、InnoDB数据页结构

2.1 局部性原理

2.2 InnoDB的数据页格式

三、InnoDB的行格式

3.1 Compact行格式

3.1.1 变长字段长度列表

3.1.2 NULL值列表

3.1.3 记录头信息

3.1.4 记录的真实数据

3.2 数据溢出问题

3.2.1 行溢出的数据

3.2.2 记录中的数据太多产生的溢出

3.3 Dynamic和Compressed行格式

四、MySQL索引底层数据结构与算法

4.1 索引到底是什么

4.1.1 索引的优点

4.1.2 索引的缺点

4.2 索引的常见模型

4.2.1 哈希表

4.2.2 有序表

4.2.3 二叉树搜索树

4.2.4 红黑树

4.2.5 B树

4.2.6 B+树

4.2.7 B树与B+树的差别

4.3 索引的代价

4.3.1 空间上的代价

4.3.2 时间上的代价

4.4 索引模型总结

一、MySQL架构图

<figcaption> MySQL架构图 </figcaption>

 

存储引擎负责对表中的数据的进行读取和写入，常用的存储引擎有InnoDB、MyISAM、Memory等，不同的存储 引擎有自己的特性，数据在不同存储引擎中存放的格式也是不同的，比如Memory都不用磁盘来存储数据。

在InnoDB中，数据会存储到磁盘上，在真正处理数据时需要先将数据加载到内存，表中读取某些记录时， InnoDB存储引擎不需要一条一条的把记录从磁盘上读出来，InnoDB采取的方式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB中页的大小一般为 16 KB，也就是说，当需要从磁盘中读数据时每一次最少将从磁盘中读取16KB的内容到内存中，每一次最少也会把内存中的16KB内容写到磁盘中。

 

二、InnoDB数据页结构

数据库之所以要以页结构来存储，这还要从操作系统中学的分页管理来说起。

首先就就涉及到一个局部性原理

2.1 局部性原理

三种不同类型的局部性:

  • 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。
  • 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与正在使用的信息在空间地址上是临近的。
  • 顺序局部性（Order Locality）：在典型程序中，除转移类指令外，大部分指令是顺序进行的。顺序执行和非顺序执行的比例大致是5:1。此外，对大型数组访问也是顺序的。指令的顺序执行、数组的连续存放等是产生顺序局部性的原因。

 

也就是说当CPU取到硬盘中的某一条数据或者执行了某一条指令，那么接下来大概率会再取它附近的数据或顺序执行后面的指令，或者该数据在未来的一段时间内会再次被访问，这样我们就先把该数据附近的数据全都放到一个页中，每次从硬盘往内存中取数据直接将一页的数据全部取出来放到内存，这要就将该数据附近的数据也取到了内存中，以后如果需要用就可以直接从内存中获取了，减少了IO操作，提高了性能效率。

这个原理放到数据库中也是一样，数据库中的数据就是存到硬盘中的，但是执行查询操作，修改操作都是需要借助CPU来实现的。

比如要查询a>10的数据，如果索引使用普通的平衡二叉搜索树结构，数据库就会把相关表中的数据一行行从硬盘读取到内存，然后再通过CPU来判断a字段是不是大于10来判断该行数据是不是我们想要的。每一次从硬盘中取出数据放到内存都是一次IO操作，这么频繁的IO操作就对导致效率极低。

 

如果使用基于页结构来管理，过程就变成了这样：

在硬盘中存储着以页为组织单位的索引树，查找a>10的数据，先从已经预加载到内存的根页开始判断，看看相关数据需要到哪一个子页去找，定位好了子页，进行一次IO操作，根据地址将指向的这个子页从硬盘中读取到内存中，这是一次IO操作，因为B+树是以也为组织单位，一页会有很多数据，而且还是一个多叉树，就会使树的高度很低，数的高度变低就会使IO操作大大减少。因为大量的比较操作已经在内存中的页里完成了，也就大大减少了IO操作（将数据从硬盘中读取到内存中的操作），提高了数据库的检索效率。关于B+树和在页内部的比较过程会在下文进行详解。

操作系统页的大小默认是4K，数据库中页的大小默认时16K，也就是数据库每次从硬盘中取得数据都是以16KB为单位。

 

2.2 InnoDB的数据页格式

页是InnoDB管理存储空间的基本单位，一个页的大小默认是16KB。

SHOW  GLOBAL  STATUS  like  'Innodb_page_size';

页结构：

 

名称

 

中文名

 

占用空间

 

简单描述

 

File Header

 

文件头部

 

38字节

 

页的一些通用信息

 

Page Header

 

页面头部

 

56字节

 

数据页专有的一些信息

 

Infimum + Supremum

 

最小记录和最大记录

 

26字节

 

两个虚拟的行记录

 

User Records

 

用户记录

 

不确定

 

实际存储的行记录内容

 

Free Space

 

空闲空间

 

不确定

 

页中尚未使用的空间

 

Page Directory

 

页面目录

 

不确定

 

页中的某些记录的相对位置

 

File Trailer

 

文件尾部

 

8字节

 

校验页是否完整

 

<figcaption> 向页中插入数据 </figcaption>

 

 

  • 各个数据页之间可以组成一个双向链表（就是B+树的各个页之间都按照索引值顺序用双向链表连接起来）
  • 而每个数据页中的记录又可以组成一个单向链表
  • 每个数据页都会为存储在它里边儿的记录生成一个页目录，该目录页是用数组进行管理，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录
  • 以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

 

示意图：

所以说，如果我们写select * from user where username = 'Java3y'这样没有进行任何优化的sql语句，默认会这样做：

  • 定位到记录所在的页
  • 需要遍历双向链表，找到所在的页
  • 从所在的页内中查找使用二分法查询目录找到相应的记录
  • 由于不是根据主键查询，只能遍历所在页的单链表了

很明显，在数据量很大的情况下这样查找会很慢！

 

 

三、InnoDB的行格式

一行记录可以以不同的格式存在InnoDB中，行格式分别是Compact、Redundant、Dynamic和Compressed行格式。

 

我们可以在创建或修改表的语句中指定行格式：

CREATE  TABLE   表名  (   列的信息 )  ROW_FORMAT= 行格式名称
ALTER  TABLE  表名  ROW_FORMAT= 行格式名称

行格式是表级别的，一个表就能设置一个行格式。

 

3.1 Compact行格式

由Compact行格式的示意图可以看出除了在右侧一次存储的真正的行数据，在左边还存有额外的信息。

 

记录的额外信息

这部分信息是服务器为了描述这条记录而不得不额外添加的一些信息，这些额外信息分为3类，分别是：

  • 变长字段长度列表
  • NULL值列表
  • 记录头信息

 

3.1.1 变长字段长度列表

MySQL支持一些变长的数据类型，比如VARCHAR(M)、VARBINARY(M)、TEXT类型，BLOB类型，这些数据类型修饰列称为变长字段，变长字段中存储多少字节的数据不是固定的，所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。在Compact行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表。

CHAR 是一种固定长度的类型， VARCHAR 则是一种可变长度的类型。VARCHAR(M)， M 代表最大能存多少个字符。 ( MySQL5.0.3 以前是字节，以后就是字符 。 在新版本的mysql中char(n)和varchar(n)中的n表示的都是字符数 )
注意：这里面存储的变长长度和字段顺序是反过来的。比如两个varchar字段在表结构的顺序是a（10），b（15）。那么在变长字段长度列表中存储的长度顺序就是15，10。是反过来的。

 

3.1.2 NULL值列表

Compact行格式会把可以为NULL的列统一管理起来，存一个标记为在NULL值列表中，如果表中没有允许存储 NULL 的列，则 NULL值列表也不存在了。之所以要存储NULL是因为数据都是需要对其的，如果没有标注出来NULL值得位置，就有可能在查询数据的时候出现混乱。如果使用一个特定的符号放到相应的数据位表示空置的话，虽然能达到效果，但是这样很浪费空间，所以直接就在行数据得头部开辟出一块空间专门用来记录该行数据那些是非空数据，哪些是空数据，格式如下：

  • 二进制位的值为1时，代表该列的值为NULL。
  • 二进制位的值为0时，代表该列的值不为NULL。

 

例如：字段 a b c 其中a是主键，在某一行中存储的数依次是 a=1 b=null c=2

那么Compact行格式中得NULL值列表中存的10。第一个1表示b是null，第二个0表示c不为null。这里之所以没有a是因为数据库会自动跳过主键，因为主键肯定是非NULL且唯一的，在NULL值列表的数据中就会自动跳过主键。

 

3.1.3 记录头信息

除了变长字段长度列表、NULL值列表之外，还有一个用于描述记录的记录头信息，它是由固定的5个字节组成。 5个字节也就是40个二进制位，不同的位代表不同的意思，如下表：

 

名称

 

大小（单

位：bit）

 

描述

 

预留位1

 

1

 

没有使用

 

预留位2

 

1

 

没有使用

 

delete_mask

 

1

 

标记该记录是否被删除

 

min_rec_mask

 

1

 

B+树的每层非叶子节点中的最小记录都会添加该标记，目的是为了加快检索速度

 

n_owned

 

4

 

表示当前记录拥有的记录数

 

heap_no

 

13

 

表示当前记录在记录堆的位置信息

 

record_type

 

3

 

表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录

 

next_record

 

16

 

表示下一条记录的相对位置

 

3.1.4 记录的真实数据

记录的真实数据除了我们自己定义的列的数据以外，还会有三个隐藏列：

 

列名

 

是否必须

 

占用空间

 

描述

 

row_id

 

否

 

6字节

 

行ID，唯一标识一条记录

 

transaction_id

 

是

 

6字节

 

事务ID

 

roll_pointer

 

是

 

7字节

 

回滚指针

实际上这几个列的真正名称其实是：DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR。

一个表没有手动定义主键，则会选取一个Unique键作为主键，如果连Unique键都没有定义的话，则会为表默认添加一个名为row_id的隐藏列作为主键。所以row_id是在没有自定义主键以及Unique键的情况下才会存在的。

剩下的事务ID和回滚指针在【MySQL】MySQL的锁与事务隔离级别详解 会有讲解。

 

3.2 数据溢出问题

3.2.1 行溢出的数据

VARCHAR(M)类型的列最多可以占用65535个字节。其中的M代表该类型最多存储的字符数量，如果我们使用 ascii字符集的话，一个字符就代表一个字节，我们看看VARCHAR(65535)是否可用：

mysql>  CREATE  TABLE  varchar_size_demo(
    c  VARCHAR(65535)
 )  CHARSET=ascii  ROW_FORMAT=Compact;

ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have  to  change  some  columns  to  TEXT&nbs***bsp; BLOBs

 报错信息表达的意思是：MySQL对一条记录占用的最大存储空间是有限制的，除BLOB或者TEXT类型的列之外， 其他所有的列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过65535个字节。这个65535个字节 除了列本身的数据之外，还包括一些其他的数据，以Compact行格式为例，比如说我们为了存储一个VARCHAR(M)类型的列，其实需要占用3部分存储空间：

  1. 真实数据
  2. 变长字段真实数据的长度
  3. NULL值标识

 

如果该VARCHAR类型的列没有NOT NULL属性，那最多只能存储65532个字节的数据，因为变长字段的长度占用 2个字节，NULL值标识需要占用1个字节。

mysql>  CREATE  TABLE  varchar_size_demo(
    c  VARCHAR(65532)
)  CHARSET=ascii  ROW_FORMAT=Compact;

Query OK, 0 rows affected (0.02 sec)

CREATE  TABLE  
varchar_size_demo( 
	c  VARCHAR(65533)  not  null
)  CHARSET=ascii  ROW_FORMAT=Compact; 
Query OK, 0 rows affected (0.02 sec)

 

3.2.2 记录中的数据太多产生的溢出

一个页的大小一般是16KB，也就是16384字节，而一个VARCHAR(M)类型的列就最多可以存储65533个字节，这样就可能出现一个页存放不了一条记录。 在Compact和Reduntant行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后记录的真实数据处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页。

 

Compact和Reduntant行格式对于这种一个页都放不下一行数据的情况会进行分页存储，具体的格式就是在原本记录真实数据地行中先存一部分数据，然后后面添加一个指向另一个页的指针，剩余的数据就被存储到另一个页中。这称为页的扩展，格式如下：

 

 

3.3 Dynamic和Compressed行格式

这两种行格式类似于COMPACT行格式，只不过在处理行溢出数据时有点儿分歧，它们不会在记录的真实数据处存储一部分数据，而是把所有的数据都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。另外， Compressed行格式会采用压缩算法对页面进行压缩。

 

四、MySQL索引底层数据结构与算法

4.1 索引到底是什么

索引是帮助MySQL高效获取数据的排好序的数据结构，索引存储在文件里。

一句话简单来说，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本 500 页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，那我估计你可得找一会儿。同样，对于数据库的表而言，索引其实就是它的“目录”。

 

在讲解索引常见模型之前先复习一下磁盘存取原理：

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间

每一次从磁盘读取数据都要靠磁盘的旋转，以及磁头的寻道来读取指定扇区的数据，这是一个很耗时的过程，也就是一次IO操作。所以提高搜索效率的重要手段就是减少IO操作次数。

  • 寻道时间(速度慢，费时)
  • 旋转时间(速度较快)
<figcaption> 磁盘结构图 </figcaption>

 

4.1.1 索引的优点

  1. 极大地加速了索引过程，减少IO次数
  2. 创建唯一索引，保证了数据库表中的唯一性
  3. 加速了表与表之间的连接
  4. 针对分组和排序检索时，能够显著减少查询查询中的分组和排序时间

 

4.1.2 索引的缺点

  1. 索引表占据物理空间
  2. 数据表中的数据增加、修改、删除的同时需要去动态维护索引表，降低了数据的维护速度

 

4.2 索引的常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多，这里我先给你介绍几种常见、也比较简单的数据结构，它们分别是：

  • HASH
  • 有序表
  • 二叉树
  • 红黑树
  • BTREE
    • B树
    • B+树

 

4.2.1 哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况（哈希碰撞）。处理这种情况的一种方法是，拉出一个链表。

假设，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

<figcaption> 哈希表示意图 </figcaption>

 

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中四个 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

你可以设想下，如果你现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须全部扫描一遍了。

所以哈希也是有很多局限的：

  • 哈希索引是无序的所以不能用于排序order by，group by 后面
  • 由于存的不是索引值，而是映射而成的hash值，所以也不支持范围查找，前缀匹配和联合索引的最左匹配原则

所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。像一些范围查询的场景就不是很适用。

 

InnoDB支持哈希索引，但是主流的还是使用B+树索引比较多，对于哈希索引，InnoDB引擎会根据索引值使用的频繁内部自动的在B+Tree索引上创建哈希索引，用户无法控制或者配置，不过可以关闭该优化特

 

4.2.2 有序表

而有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

<figcaption> 有序数组示意图 </figcaption>

这里我们假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。

同时很显然，这个索引结构支持范围查询。你要查身份证号在[ID_card_X, ID_card_Y]区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。

如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

 

4.2.3 二叉树搜索树

二叉搜索树也是课本里的经典数据结构了。还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

<figcaption> 二叉搜索树示意图 </figcaption>

二叉搜索树的特点是：在普通二叉树的基础上，规定每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。

但是如果只是一个二叉搜索树，如果一直按增序插入数据，那么这颗二叉搜索树就会失衡，导致树的高度很大，大大降低了查询效率，如下图：

比如我想查询0007这个数，那么就需要经历6次比较查询才能得到结果。

 

为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树（AVL）。为了做这个保证，更新的时间复杂度也是 O(log(N))。下面就引入一种平衡二叉树---红黑树。

 

4.2.4 红黑树

首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。它同时满足以下特性：

  1. 每个节点要么是黑色，要么是红色
  2. 根节点是黑色
  3. 如果节点是红色的，那么它的子节点必须是黑色的（反之，不一定需要成立）
  4. 从根节点到叶节点或空子节点的每条路径，都包含相同数目的黑色节

 

那么为什么当满足以上性质时，就能保证最长路径不超过最短路径的二倍了呢？我们分析一下：

当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。

【数据结构】红黑树详解（插入与删除）

可是红黑是还是一个二叉树，它的深度会随着数据量的增多急剧升高，这样查询的效率也会很低。但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的。

 

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘（IO操作）。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。这也就引入了后面的B树和B+树

 

4.2.5 B树

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。其实阶数和度数本质是一样的，因为m阶树规定每个结点最多有m-1个关键字。而度数规定的是一个节点内有多少个关键字，所以本质是一样的。下文会有度数和阶数的混用，请注意区分。

 

B-Tree

  • 度(Degree)-节点的数据存储个数
  • 叶节点具有相同的深度
  • 叶节点的指针为空
  • 节点中的数据key从左到右递增排列

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，也就是索引值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。除了key和data外，节点还存储了指向孩子节点的指针。那么B-Tree是满足下列条件的数据结构：

  1. 每个结点最多有m-1个关键字。
  2. 根结点最少可以只有1个关键字。
  3. 非根结点至少有Math.ceil(m/2)-1个关键字。
  4. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。（注意这里和B+树有点不同，B+树右子树时大于等于，因为B+树会冗余存储数据）
  5. 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

 

由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败

关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

 

4.2.5.1 B树的插入操作

插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

  1. 根据要插入的key的值，找到叶子结点并插入。
  2. 判断当前结点key的个数是否小于d，若满足则结束，否则进行第3步。
  3. 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。（页分裂）

 

下面以阶数为5的树为例，介绍B树的插入操作，在阶数为5的B树中，结点最多有4个key,最少有2个key

a）在空树中插入39 

此时根结点就一个key，此时根结点也是叶子结点

 

b）继续插入22，97和41

根结点此时有4个key

 

c）继续插入53

插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

 

d）依次插入13，21，40，同样会造成分裂，结果如下图所示。

 

e）依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。

 

f）插入key值为26的记录，插入后的结果如下图所示。

当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。

进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

分裂后当前结点指向新的根，此时无需调整。

 

g）最后再依次插入key为17,28,29,31,32的记录，结果如下图所示。

在实现B树的代码中，为了使代码编写更加容易，我们可以将结点中存储记录的数组长度定义为m而非m-1，这样方便底层的结点由于分裂向上层插入一个记录时，上层有多余的位置存储这个记录。同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

一般来说，对于确定的m和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。但是分配固定结点大小的方***存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。

而且将数据和索引值都在节点中存放也会导致一个页能存储的索引节点不多，度数较低，使树得宽度不够大，高度变高，高度越高，检索效率越低。

 

 

4.2.5.2 B树的删除操作

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

  1. 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思，也就是按照索引值的顺序，要删除节点的索引值的下一个索引值节点就是后继key）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
  2. 该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
  3. 如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。（页合并）
    否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
    有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

 

下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key

a）原始状态

 

b）在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

 

c）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

 

d）在上述情况下接着32，结果如下图。

当删除后，当前结点中只key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

当前结点key的个数满足条件，故删除结束。

 

e）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

合并后结点当前结点满足条件，删除结束。

 

对于B树的检索效率低和节点使用率低的情况，最终引入了B+树来组织索引树，B+树也是现在存储引擎中使用最广泛的索引结构。

 

4.2.6 B+树

B+Tree(B-Tree变种)

  • 非叶子节点不存储data，只存储key，可以增大度
  • 叶子节点不存储指针
  • 顺序访问指针，提高区间访问的性能
  • B+树也规定叶子节点的深度必须一致

B+Tree索引的性能分析

  • 一般使用磁盘I/O次数评价索引结构的优劣
  • 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存，比如会将根页预载入进内存。
  • 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
  • B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
  • B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)

 

4.2.6.1 B+树的定义

 

各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。上图就是一颗阶数为4的B+树。

除此之外B+树还有以下的要求。

  1. B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。非根节点的关键字最少有2个。
  2. B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
  3. m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。
  4. 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
  5. 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

 

4.2.6.2 B+树的插入操作

  1. 若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
  2. 针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
  3. 针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

 

下面是一颗5阶B树的插入过程，5阶B数的结点最少2个key，最多4个key。

a）空树中插入5

 

b）依次插入8，10，15

 

c）插入16

插入16后超过了关键字的个数限制，所以要进行分裂（页分裂）。在叶子结点分裂时，分裂出来的左结点2个记录，右边3个记录，中间key成为索引结点中的key，分裂后当前结点指向了父结点（根结点）。这里就会冗余的存储10这个索引值。结果如下图所示。

当然我们还有另一种分裂方式，给左结点3个记录，右结点2个记录，此时索引结点中的key就变为15。

 

d）插入17

 

e）插入18，插入后如下图所示

当前结点的关键字个数大于5，进行分裂。分裂成两个结点，左结点2个记录，右结点3个记录，关键字16进位到父结点（索引类型）中，将当前结点的指针指向父结点。

当前结点的关键字个数满足条件，插入结束。

 

f）插入若干数据后


g）在上图中插入7，结果如下图所示

当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

当前结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，根页最少的结点数可以是1。结果如下图所示。

当前结点的关键字个数满足条件，插入结束。

 

4.2.6.3 B+树的删除操作

如果叶子结点中没有相应的key，则删除失败。否则执行下面的步骤

  1. 删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束,否则执行第2步。
  2. 若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。
  3. 若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。
  4. 若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第5步
  5. 若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步
  6. 当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。

 

下面是一颗5阶B树的删除过程，5阶B数的结点最少2个key，最多4个key。

a）初始状态

 

b）删除22,删除后结果如下图

删除后叶子结点中key的个数大于等于2，删除结束

 

c）删除15，删除后的结果如下图所示

删除后当前结点只有一个key,不满足条件，而兄弟结点有三个key，可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9，删除结束。

 

d）删除7，删除后的结果如下图所示

当前结点关键字个数小于2，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并（页合并），并删除父结点中的key，当前结点指向父结点。

此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。

目前B+树是应用最广泛的一种索引结构。

 

4.2.7 B树与B+树的差别

  1. B树的同一键不会出现多次，可能在叶子节点上也可能在非叶子节点上；  b+树的键一定会出现在叶子节点上，同时也可能在非叶子节点上重复出现。
  2. 简单的说，b+树的非叶子节点存储的都是键值，键值对应的具体数据都存储在叶子节点上。
  3. b数据的每个节点存储的是真实数据，会导致每个节点的存储的数据量变小，所以整个b树的高度会相对变高。随着数据量的变大，维护代价也增加； b+树的非叶子节点只存储的是键值，相对而言，一个非叶子节点存储的记录个数要比b树多的多。
  4. b+树是横向扩展，随着数据增加，会变成一个矮胖子，b树是纵向扩展，最终树的高度越来越高（高瘦子）。
  5. b树的查询效率与键在b树的位置有关系，在叶子节点的时候最大复杂度与b+树相同；b+树复杂度对某个建成的树是固定的。
  6. b树的键的位置不固定并且整个树结构中只出现一次，增删改查操作复杂度逐渐加；b+树中非叶子节点对于叶子节点来说就像一个索引，增删改的时候只要找到键值（索引）的位置，再一层层的向下找即可，只有在遇到一个节点存储满了会对b+树分裂。
  7.  b树种所有的数据都只存储一份；b+树除存储了所有数据的叶子节点外，还有之存储键值数据的非叶子节点。所以，b+树比b树会多占存储空间，多占的空间就是b+树的非叶子节点的所有空间。

 

4.3 索引的代价

以目前应用最广泛的B+树为例。

4.3.1 空间上的代价

一个索引都对应一棵B+树，树中每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，所以一个索引也是会占用磁盘空间的。建立的索引越多，在硬盘中冗余存放的数据也就越多，占用的空间就越大。

 

4.3.2 时间上的代价

索引是对数据的排序，那么当对表中的数据进行增、删、改操作时，都需要去维护修改内容涉及到的B+树索引。 所以在进行增、删、改操作时可能需要额外的时间进行一些记录移动，页面分裂、页面回收等操作来维护好排序。所以建立索引前需要考虑它的维护成本。

 

4.4 索引模型总结

不管是哈希还是有序数组，或者 N 叉树，它们都是不断迭代、不断优化的产物或者解决方案。数据库技术发展到今天，跳表、LSM 树等数据结构也被用于引擎设计中，这里我就不再一一展开了。

你心里要有个概念，数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库，我们需要先关注它的数据模型，这样才能从理论上分析出这个数据库的适用场景。

在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。由于 InnoDB 存储引擎在 MySQL 数据库中使用最为广泛，所以下面我就以 InnoDB 为例，该存储引擎最后选择了B+树作为索引结构。我们再重新梳理一下B+树的相关知识点。

InnoDB存储引擎中，因为主键索引使用的是聚集索引，所以在插入数据的时候还需要额外的对索引树进行维护。在插入数据的时候，每插一条数据就会按照索引值的顺序来进行重新排序，将数据插入到它应该在的位置。这样其实插入效率也就变低了。因为InnoDB中聚集索引的数据和主键索引树存在一起，就在叶子节点，所以为了所有数据都是按照顺序排放，在插入到新数据的时候自然要重新组织数据的位置，会出现很多数据页的在存储器中的位置变换，为了保证B+树的性质需要进行页页分裂，这是一个很消耗性能的过程。所以在插入数据的时候按照主键值的顺序来进行插入，这样就会减少这种数据页位置的移动，提高插入效率。

B+树所有的非叶子结点的索引值在叶子节点都冗余存储了一份，而且叶子节点都是都是一个递增顺序，叶子节点之间都用指针连接了起来能够加快搜索效率。

先创建表得时候就会先创建第一页，向数据库中插入数据的时候就会先往第一页插入，当第一页达到度数后，就会进行页分裂，，它的过程是这样的：先将这个第一页复制一份，然后作为左结点，然后再开辟一个右节点，再按照左小右大的原则将原本在第一页装不下的数据分别放到新建立的左右两个子页，然后将原来的第一页作为一个目录页。这样的作用就是保证B+树得第一页的地址是不会改变的，采用了一个永远都不会改变的查询入口，这样每次对这个表查询直接就从这个固定的地址开始查询就可以了。非根页这样分裂也能保证他们的父页指向他们的指针不需要变动，减轻维护B+树的成本。

B+树的核心思想就是逐渐的开辟新的页通过增加树宽度来分摊一个页所存储的数据数。将数据页转化为目录页，然后将原本的数据放到有创建好的两个数据页中。一旦一个页超过的度数，也就是占用的大小已经超过了16K，那就会执行上面的过程，注意，第一页下面的子页最多也到指定的度数度数了，如果在变得多的就由下面的子页再接着去页分裂就行了，来分摊上面多出来的数据。由于B+数的原理，B+数是横向扩展，一层能存很多数据，所以它的树高最多也就4-5层。

B+数比B数的优点就是将原本放在每个结点页的数据全都转移到了叶子节点，这个样子就能保证每个页能存更多的目录项，就能使树的横向扩展更大，树的宽度越大，深度降低，这样就能有效的提高搜索效率。因为毕竟深度越大，要进行的分支判断就越多，效率就越低。

搜索二叉树每次都要从硬盘读取，要进行IO操作，深度越高效率越低。B树是把一个节点加载到内存中取查找，最多只读取磁盘三次，而且根节点是会预热加载到内存的。

 

B+树索引总结：

  1. 每个索引都对应一棵B+树。用户记录都存储在B+树的叶子节点，所有目录记录都存储在非叶子节点。
  2. InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。
  3. 可以为指定的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。
  4. B+树中页之间都是按照索引列值从小到大的顺序排序而组成了双向链表（B+树的每个页其实都按照索引顺序用双向链表连接了起来），而且每个页内的记录（不论是索引项还是数据项）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。
  5. 通过索引查找记录是从B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了页目录，所以在这些页面中的查找非常快。每次都是将一页放入内存中去进行操作，所以页内部的检索非常快。

其他相关文章：【MySQL】MySQL的存储引擎和索引详解（聚集索引和非聚集索引）
                         【MySQL】InnoDB存储引擎，MyISAM存储引擎，聚集索引，非聚集索引，主键索引，二级索引他们之间的关系梳理
                         【MySQL】MySQL的锁与事务隔离级别详解 
                         【MySQL】MySQL分库分表详解
                         【MySQL】主从复制实现原理详解

参考资料：《高性能MySQL》(第3版)
                    B树和B+树的插入、删除图文详解
                  《MySQL实战45讲》林晓斌