聊聊B-Tree的Golang实现

这次准备出一个关于B树的合集。在第一部分，先来介绍下B树的基本概念。

B树与bst等二叉树不同，B树是多叉树，而且B树是自平衡树。B树的Search、Insert、Remove算法时间复杂度都是O(log N)。

B树常常用于数据库。数据库常常数据量巨大，因此不可能光放到内存中，需要放到硬盘中进行存储。而硬盘是块设备，就是一次读取一块区域，而B树是多叉树，因此有多个key，所以一块区域就可以包含多个key。另外硬盘相比内存比较慢，B树因为是多叉树相对于二叉树更矮，所以能更多的减少硬盘交互的次数。

B树有一些属性，我更愿意称这些属性为规约或者说规约形成的结果：

1、B树用来衡量每个节点(node)的大小的度量衡被称为度(degree，简写为t)和秩(order，简写为m)。度和秩是不同的两个角度，度是说B树的任意节点(除了root节点)至少有t个分叉(至多2t个分叉)，秩是说B树的任意节点(除了root节点)至多有m个分叉。后续将以度为度量衡进行解释B树。

2、因为任意节点(除了root节点)至少有t个分叉，所以任意节点(除了root节点)至少有t-1个key。

3、与2同理，任意节点(除了root节点)至多有2t-1个key。可见是个奇数。

4、任意节点中的key都是按升序排列的。所以可以在节点上方便的使用二分查找。

5、任意两个key k1和k2中间的子树的key都在k1到k2的范围内。如上面的图中所示。

6、Insert只会发生在叶子节点。

7、B树的Search、Insert和Remove，都是从root节点出发的。

8、所有的叶子节点都在同一level。

9、与其他自平衡树一样，B树的Search、Insert、Remove算法时间复杂度都是O(log N)。