MySQL底层存储B-Tree和B+Tree原理分析

1.B-Tree的原理分析

（1）什么是B-Tree

• B-树，全称是 Balanced Tree，是一种多路平衡查找树。

• 一个节点包括多个key (数量看业务)，具有M阶的B树，每个节点最多有M-1个Key。

• 节点的key元素个数就是指这个节点能够存储几个数据。

• 每个节点最多有m个子节点，最少有M/2个子节点，其中M>2。

• 数据集合分布在整个树里面，叶子节点和非叶子节点都存储数据；类似在整个树里面做一次二分查找。

• B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data）。

• 实际业务中B树的阶数一般大于100，存储大量数据，B树高度也会很低，查询效率会更高。

• 备注

  • 每个节点拥有最多的子节点，子节点的个数一般称为阶。

  • 阶：m阶是代表每个节点最多有m个分支（子树）。

  • 树的度：这棵树里面节点最大的度。

  • 节点的度：当前节点有几个子节点。

（2）B树插入原理

• 每个节点的数据都是顺序存储，具有M阶的B树，树的阶数表示每个结点最多可以有多少个子结点

（3）B树的应用场景

• 在数据库中，B树用来维护索引，用来提高查询效率，一个节点可以存储整个页（即磁盘块）
• 在文件系统中，B树用来存储文件的目录信息，提高文件的访问效率
• 在操作系统中，B树可以用来存储内存管理信息，提高内存的分配效率

（4）思考：3层的B树，阶数为1024，最多容纳多少个元素？

• B树的阶数表示每个结点最多可以有多少个子结点，因此B树的阶数为1024，表示每个结点最多可以有1024个子结点

• 由于B树的3层，因此根结点可以有1024个子结点，每个子结点又可以有1024个子结点

• 因此一个3层的B树，阶数为1024，B树的每一层的节点数都是阶数的幂次方

• 计算总容量 把每一层的节点数相加 即1024¹⁺¹⁰²⁴2+1024^3 大约是 11亿个节点，假如每个节点放一个元素就是11亿个

• 所以在10亿个数据中找目标值，常规小于3次磁盘IO即可找到目标值，比平衡二叉树的30次提升了不少

  • 平衡二叉树的高度就等于每次查询数据时磁盘 IO 操作的次数。

  • 10亿的数据量，log2(N)约等于30次磁盘IO，

    • log2(N) 相当于2的多少次方（立方）等于N，例：log2 (8）= 3
    • 2的30次方=1073741824，所以就是30次磁盘IO

2.B+Tree的原理分析

（1）什么是B+Tree

• 是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，同等存储空间下比B-Tree存储更多key
• 非叶子节点不对关键字记录的指针进行保存，只进行数据索引 , 树的层级会更少 , 所有叶子节点都在同一层,
• 叶子节点的关键字从小到大有序排列，叶子节点之间用指针连接, 构成有序链表（稠密索引）
• B+树上每个非叶子节点之间是一个双向链表进行链接，而叶子节点中的数据都是使用单向链表链接
• 查找特点
  • 当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找
  • 继续沿着关键字的指针向下，每次查询必须到叶子节点才能真正获取到相关数据
  • B+Tree叶子节点相连接，对树的遍历就是只需要 一次线性遍历叶子节点
  • 由于叶子节点的数据是顺序排列，方便区间查找
  • 在B+树完成范围查找，排序查找，分组查找，去重查找 比B树效率也比较高

（2）B+Tree插入流程解析

• 总结

  • B树和B+树的最大区别在于非叶子节点是否存储数据

  • B+树非叶子节点只是当索引使用，同等空间下B+树存储更多key

  • B树,非叶子节点和叶子节点都会存储数据，找到对应节点就有对应的数据

  • B+树, 只有叶子节点才会存储数据,存储的数据都是在一行上，找到非叶子节点的key，还需要继续找到叶子节点才可以获取数据

  • B树的节点包括了key-value，所以找到对应的key即可找到对应的value，不用在继续寻找

  • 两种树各有优缺点和应用场景

3.B+Tree树应用之Mysql索引底层原理剖析

• 背景

  • Mysql数据库是大家用最多的，查询是最高频使用的操作

  • 在多数数据库的设计里面，会用B-Tree或B+Tree做索引提高查询效率

• 基于一张数据库的表数据进行查询（类似mysql的user表）

• 构建索引：id用做key，然后data是数据的存储地址

内存地址	id	phone	name	Age
0xFS	843	13820835467	张三	43
0xER	984	15738235423	李四	20
0x32	4212	12152354223	王五	18
0x93	1000	12152356324	赵六	30
0xAP	2341	18735622097	李祥	19
0xSQ	… 1千万条数据	…	…	…

• 精确查找 id=2341的数据 select * from user where id = 2341

  • 未使用索引

    • 自上而下查找数据，一行行遍历，5次才找到数据

  • 使用索引

    • id建立主键索引（B+Tree结构），对应的数据存储数据的地址，2次找到数据，且数据量越多效果越明显
    • 根节点是常驻内存的，不需要进行IO操作

• 范围查找 id>1000 和 id < 4212 的用户

  • 未使用索引

    • 自上而下查找数据，一行行遍历

  • 使用索引

    • id建立主键索引（B+Tree结构），由于本身是有序链表，所以顺序查找即可

• Mysql的InnoDB中的索引结构与MyISAM的索引结构的区别

• InnoDB引擎,表数据文件按B+Tree组织的，叶节点data域保存完整行数据, 树上的key就是主键, 以主键构建的B+树索引

  • 这种索引叫做聚集索引（聚簇索引 clustered index）

  • 聚簇索引一般为主键索引，而主键一个表中只能有一个，所以聚集索引一个表只能有一个

  • 聚簇索引叶子节点存储的是行数据，而非聚簇索引叶子节点存储的是聚簇索引（通常是主键 ID）

• MyISAM引擎：索引文件和数据文件是分开的，索引结构的叶子节点放的是指向数据的主键（或者是地址）构建的B+树索引

  • 这种索引叫做非聚集索引、二级索引、辅助索引（非聚簇索引 nonclustered index）
  • 非聚集索引一个表可以存在多个
  • 叶子节点中保存的不是实际数据，而是主键，获得主键值后去聚簇索引中获得数据行

• 注意

  • 非聚簇索引的叶子节点上存储的并不是真正的行数据，而是主键 ID或记录的地址

  • 当使用非聚簇索引进行查询时，会得到一个主键 ID，再使用主键 ID 去聚簇索引上找真正的行数据，把这个过程称之为回表查询

  • 所以聚簇索引查询效率更高，而非聚簇索引需要进行回表查询，性能不如聚簇索引

  • 非聚簇索引的叶子节点上存储的并不是真正的行数据，而是主键 ID或记录的地址

  • 当使用非聚簇索引进行查询时，会得到一个主键 ID，再使用主键 ID 去聚簇索引上找真正的行数据，把这个过程称之为回表查询

  • 所以聚簇索引查询效率更高，而非聚簇索引需要进行回表查询，性能不如聚簇索引