B Tree

对于一个数据的查找，之前说过二叉树搜索树，以及为了使得其平均效率更好，提出的各种各样的平衡二叉树的概念，不赖

不过假设我们对于一个节点的访问，是磁盘 IO，即从磁盘中读取数据再载入内存，这个操作就比较贵，不可忽略。所以在尽可能的减少查找次数的同时，也希望可以减少磁盘 IO 的次数 —— 那么不妨把这棵搜索树“变矮变胖”，一次读取节点的同时就载入一批数据，减少多次磁盘 IO

于是就有 B-Tree（以及后来的 B+ / B* 的优化等），不过先简单看下 B-Tree

对于一个节点，不再是简单的存储当前的 Value，以及左右孩子 —— 现在存储一批已经排好序的数据，以及一堆孩子（

假设当前的节点存储了 ——

[1, 14, 51]

那么实际上它可以把整个搜索空间划分成 ——

<1, 1~14, 14~51, >51

四个空间，分别对应当前节点的四个孩子，这样如果待查找的数据不在当前层，也可以非常方便的归到子树去进行查找。与此同时，也可以非常简单的得到一个数学关系 —— 如果一个节点可以存储 $k$ 个 key，那么其最多可以拥有 $k+1$ 个孩子

如果一个节点可以拥有几百个孩子，那么整颗树的高度就会非常小，从而减少节点访问的次数，实现目的

查找

和普通的二叉搜索树非常的相似，只是把和当前节点的 Value 进行比较换成了一次二分查找，例如 ——

                 [20 | 50]

          [5 10]   [30 40]   [60 70]

对于这样一棵树，我们要查找 40，首先在根节点 [20, 50] 中做一次二分查找，发现 20 < 40 < 50，于是往 [30, 40] 这个子节点中进行查找

插入

假设所有层级都不是满的，那么插入也很简单，直接递归查找到所在区间的叶子节点，然后再做一次二分插入即可

可惜，现实当中要考虑一个节点的最大容量问题，所以需要 Split 操作 —— 现在假设有如下已满的节点

[10, 20, 30]

由于 20 在“中间”，于是把它提升到父节点

       [20]
      /    \
   [10]    [30]

那么对于一般的 $2t-1$ 的容量的节点来说，就是左右各 $t-1$ 个 Key 保留，对于中间的第 $t$ 个 Key 提升到父节点中。这样即保证了平衡，而且也保证了有序的区间划分性质，不赖

但是此时会遇到两个边界情况 ——

第一个比较简单，就是对于根节点的 Split 操作 —— 对于需要提升的节点来说，直接新建一个节点作为父节点，然后再执行插入操作即可（此时所有的孩子高度都 +1，依旧不破坏平衡）

第二个略有复杂 —— 在对于当前节点执行 Split 操作的时候，想要向父亲插入一个新数据的时候，发现父节点已经满了

这略有点棘手，也就是需要层层迭代上去进行 Split 操作，那么我们需要额外对每一个孩子维护其父亲的位置信息？？！这很不优雅，于是我们希望可以直接规避掉这个边界情况 —— 即在每一次插入的时候，如果当前节点要走向的孩子已经满了，则对该孩子进行 Split 操作，这样在往孩子插入数据的时候，一定保证其不是已满的节点，可以直接插入

块

导入部分其实也说明了，B 树主要降下来的是访问数据的成本而不是单纯的内存查找成本

比如数据库通常是按 Page 进行数据的组织；又或是文件系统按 Block 对外部存储数据进行管理；如果对其进行大量的随机 IO 操作，很贵，于是可以考虑对把一个 Node 映射到一个固定大小的 Page（以 Page 作为例子）—— 这样经过一次 IO 操作之后，就可以存入大量的索引和数据来进行查找和指向孩子的 Page 位置

这大抵就是索引系统干的事情罢，也是我们常说的操作系统中的文件系统利用的 B-Tree 的原因 —— 即面对大量的需要持久化的数据，块存储，随机 IO 很贵，多次查找等这些特征的场景，可以考虑使用 B 树家族对其进行组织