B树引入
B树（英语：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉搜索树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快访问速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
wiki 上是这么描述 B 树的, 重点在于 B 树被用作存储系统的实现上, 基于二叉搜索树天然的有序性, 实现 logn 级别的查询; 既然是用作存储系统的实现, 那么可以来推导一下, 为什么B 树会用作存储系统的实现?
想要实现 logn 级别的查询, binary search tree skiip list 都可以实现, Why B 树?
二叉搜索树
二叉搜索树天然有序, 也能达到 logn 级别的查询性能, 但是二叉搜索树, 有个很严重的问题, 如果插入的数据本身是有序的, 那二叉搜索树就会退化为链表, 要解决这个问题, 可以用 AVL Tree (Balanced binary search tree) 和 Red-Black Tree.
AVL 树
AVL Tree (Balanced binary search tree) 在二叉搜索树的基础上, 增加了自平衡的机制, 解决二叉搜索树退化为链表的问题, 但是自平衡也会带来新的问题(平衡条件必须满足所有节点的左右子树高度差不超过1), 插入时可能会触发多次的自平衡, 从而会影响数据插入的效率, 那有没有办法解决频繁的自平衡的问题呢?
红黑树
Red-Black Tree 就能做到, 红黑树通过制定一系列的规则:
- 节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL节点，空节点）是黑色的。
- 每个红色节点的两个子节点都是黑色（即从每个叶子到根的所有路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的, 平衡条件相对于 AVL 树宽松, 从而减少平衡次数, 获得更好的插入效率;
到这里, 看上去问题好像都解决了, 用红黑树就能满足存储系统的要求, 事实上确实也是这样, 很多语言的 hashmap 就是用红黑树作为底层存储实现的, 前提是这些索引结构都是在内存中, 如果这个存储系统是基于磁盘, 红黑树是否适用?
B树
文件放到磁盘上, 那么怎么快速找到文件中的数据呢?
- 首先需要减少跟磁盘的交互次数;
- 其次是存储的数据是有序的, 才能实现
logn级别的查询;
树形结构的存储, 最直接的思路就是一个node存储为一个文件, 基于这个背景, 查询的性能就直接取决于树的高度, 每一次从 parent 到 child, 都是一次磁盘 IO, 查找的文件越多, 性能越差;
如果能降低树的高度, 对应查询性能就会提高, 基于树的结构, 如何降低树的高度呢? 提高 child 的个数, 改为 m 叉树, 这样做有两个好处:
- 可以把多个节点压缩到一起, 从而减少树的高度;
- 磁盘和内存都是基于 page 的存储, 默认为 4K, 多个节点数量可以凑够4K, 提高空间利用率;
这样, B 树就诞生了,B 树本质是多路查找树, 每个节点都保存多个 key , 同时每个节点可以包含 M 个子节点, 同时也需要满足查找树的顺序性;
B+ 树
通常来说, B 树的每个节点会包含 key data 以及子节点的指针, 就这种结构而言, 是否还有优化的空间呢?
基于B 树, 想进一步优化查询效率, 还是一个重要的原则: 减少树的高度, 如果从存储上来说, 每一个节点存储为一个文件的话, 节点数量越少, 存储的文件就越少, 查询时, 跟磁盘的交互次数就越少, 如果只在叶子节点中存储数据, 其余节点只存储 key 信息, 那节点数量就能大幅减少, 从而能存储更多的数据, 树的高度也会降低, 这就是 B+ 树的思路;
同时, B+ 树数据都在叶子节点, 叶子节点还用链表连接起来, 更方便范围查询; 这个思路跟跳表很相似, 非叶子节点可以认为是叶子节点的索引;
/**
* 这是B+树非叶子节点的定义。
*
* 假设keywords=[3, 5, 8, 10]
* 4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
* 5个区间分别对应：children[0]...children[4]
*
* m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
*/
public class BPlusTreeNode {
public static int m = 5; // 5叉树
public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针
}
/**
* 这是B+树中叶子节点的定义。
*
* B+树中的叶子节点跟内部节点是不一样的,
* 叶子节点存储的是值，而非区间。
* 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
*
* k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
*/
public class BPlusTreeLeafNode {
public static int k = 3;
public int[] keywords = new int[k]; // 数据的键值
public long[] dataAddress = new long[k]; // 数据地址
public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}
参考
https://oi-wiki.org/ds/bplus-tree/
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html