数据结构与算法 / B- Tree 和 B+ Tree
一、M 阶 B- Tree（B Tree） 特点
- 根节点的 key 数量，1 <= sum <= m-1 。
- 非根节点 key 数量，m/2 <= sum <= m-1 。
- 所有节点中的 key 都按照从小到大排列。每个 key 的左子树中所有 key 都小于它，其右子树中所有的 key 都大于它。
- 所有的叶子节点都位于同一层。
- 所有节点都存有子节点的指针、索引和数据，即：key - value。
二、M 阶 B+ Tree 特点
- 根节点的 key 数量，1 <= sum <= m-1 。
- 非根节点 key 数量，m/2 <= sum <= m-1 。
- 所有节点中的 key 都按照从小到大排列。每个 key 的左子树中所有 key 都小于它，其右子树中所有的 key 都大于它。
- 所有的叶子节点都位于同一层。
- 节点分为内部节点和叶子节点。内部节点只保存子节点的指针和 key，即：索引。
- 叶子节点保存所有的 key 和 value 。
- 每个叶子节点都含有与其紧邻的叶子节点的地址，形成双向链表。
三、MySQL 选择 B+ Tree 的原因
- 每一个节点存储的 key 更多，使得查询的 IO 次数更少。因为每个节点都保存在一个页的存储空间内，其存储空间是有限的，如果 data 很大，直接导致每个节点中包含的 key 变少，tree 的深度加大，从而导致了查询时磁盘 IO 的次数增加，性能下降。
- 因为所有的 key - value 都保存在子节点中，每次查询都要到大子节点，使得查询的性能稳定。
- 所有叶子节点形成一个双向链表，方便查找。
图片原网址：https://www.cnblogs.com/vianzhang/p/7922426.html
（SAW：Game Over！）
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！