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^1+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=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 去聚簇索引上找真正的行数据，把这个过程称之为回表查询

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