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

1.B-Tree的原理分析

&＃xff08;1&＃xff09;什么是B-Tree

• B-树&＃xff0c;全称是 Balanced Tree&＃xff0c;是一种多路平衡查找树。

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

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

• 每个节点最多有m个子节点&＃xff0c;最少有M/2个子节点&＃xff0c;其中M>2。

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

• B 树相对于平衡二叉树&＃xff0c;每个节点存储了更多的键值&＃xff08;key&＃xff09;和数据&＃xff08;data&＃xff09;。

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

• 备注

  • 每个节点拥有最多的子节点&＃xff0c;子节点的个数一般称为阶。

  • 阶&＃xff1a;m阶是代表每个节点最多有m个分支&＃xff08;子树&＃xff09;。

  • 树的度&＃xff1a;这棵树里面节点最大的度。

  • 节点的度&＃xff1a;当前节点有几个子节点。

&＃xff08;2&＃xff09;B树插入原理

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

&＃xff08;3&＃xff09;B树的应用场景

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

&＃xff08;4&＃xff09;思考&＃xff1a;3层的B树&＃xff0c;阶数为1024&＃xff0c;最多容纳多少个元素&＃xff1f;

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

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

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

• 计算总容量 把每一层的节点数相加 即1024^1&＃43;10242&＃43;1024^3 大约是 11亿个节点&＃xff0c;假如每个节点放一个元素就是11亿个

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

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

  • 10亿的数据量&＃xff0c;log2(N)约等于30次磁盘IO&＃xff0c;

    • log2(N) 相当于2的多少次方&＃xff08;立方&＃xff09;等于N&＃xff0c;例&＃xff1a;log2 (8&＃xff09;&＃61; 3
    • 2的30次方&＃61;1073741824&＃xff0c;所以就是30次磁盘IO

2.B&＃43;Tree的原理分析

&＃xff08;1&＃xff09;什么是B&＃43;Tree

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

&＃xff08;2&＃xff09;B&＃43;Tree插入流程解析

• 总结

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

  • B&＃43;树非叶子节点只是当索引使用&＃xff0c;同等空间下B&＃43;树存储更多key

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

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

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

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

3.B&＃43;Tree树应用之Mysql索引底层原理剖析

• 背景

  • Mysql数据库是大家用最多的&＃xff0c;查询是最高频使用的操作

  • 在多数数据库的设计里面&＃xff0c;会用B-Tree或B&＃43;Tree做索引提高查询效率

• 基于一张数据库的表数据进行查询&＃xff08;类似mysql的user表&＃xff09;

• 构建索引&＃xff1a;id用做key&＃xff0c;然后data是数据的存储地址

• 精确查找 id&＃61;2341的数据 select * from user where id &＃61; 2341

  • 未使用索引

    • 自上而下查找数据&＃xff0c;一行行遍历&＃xff0c;5次才找到数据

  • 使用索引

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

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

  • 未使用索引

    • 自上而下查找数据&＃xff0c;一行行遍历

  • 使用索引

    • id建立主键索引&＃xff08;B&＃43;Tree结构&＃xff09;&＃xff0c;由于本身是有序链表&＃xff0c;所以顺序查找即可

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

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

  • 这种索引叫做聚集索引&＃xff08;聚簇索引 clustered index&＃xff09;

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

  • 聚簇索引叶子节点存储的是行数据&＃xff0c;而非聚簇索引叶子节点存储的是聚簇索引&＃xff08;通常是主键 ID&＃xff09;

• MyISAM引擎&＃xff1a;索引文件和数据文件是分开的&＃xff0c;索引结构的叶子节点放的是指向数据的主键&＃xff08;或者是地址&＃xff09;构建的B&＃43;树索引

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

• 注意

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

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

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

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

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

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