B 树和 B+ 树有什么区别？( 三 ) _B

当然还不算，因此还需要继续优化我们的算法。二叉搜索树，在内存中是一个高效的数据结构。这是因为内存速度快，不仅可以随机存取，还可以高频操作。注意 CPU 缓存的穿透率只有 5% 左右，也就是 95% 的操作是在更快的 CPU 缓存中执行的。而且即便穿透，内存操作也是在纳秒级别可以完成。
但是，这个逻辑在磁盘中是不存在的，磁盘的速度慢太多了。我们可以尝试把尽可能多的二叉搜索树读入磁盘，但是如果数据量大，只能读入一部分呢？因此我们还需要继续改进算法。
B 树和 B+ 树
二叉搜索树解决了连续结构插入新元素开销很大的问题，同时又保持着天然的二分结构。但是，当需要索引的数据量很大，无法在一个磁盘 Block 中存下整棵二叉搜索树的时候。每一次递归向下的搜索，实际都是读取不同的磁盘块。这个时候二叉搜索树的开销很大。
试想一个一万亿条订单的表，进行 40 次查找找到答案，在内存中不是问题，要考虑到 CPU 缓存有 90% 以上的命中率（当然前提是内存足够大）。通常情况下我们没有这么大的内存空间，如果 40 次查找发生在磁盘上，也是非常耗时的。那么有没有更好的方案呢？
一个更好的方案，就是继续沿用树状结构，利用好磁盘的分块让每个节点多一些数据，并且允许子节点也多一些，树就会更矮。因为树的高度决定了搜索的次数。

文章插图

上图中我们构造的树被称为 B 树（B-Tree），开头说过，B 这个字母具体是哪个单词或者人名的缩写，至今有争议，具体你可以查查资料。
B-Tree 是一种递归的搜索结构，与二叉搜索树非常类似。不同的是，B 树中的父节点中的数据会对子树进行区段分割。比如上图中节点 1 有 3 个子节点，并用数字 9,30 对子树的区间进行了划分。
上图中的 B 树是一个 3-4 B 树，3 指的是每个非叶子节点允许最大 3 个索引，4 指的是每个节点最多允许 4 个子节点，4 也指每个叶子节点可以存 4 个索引。上面只是一个例子，在实际的操作中，子节点有几十个、甚至上百个索引也很常见，因为我们希望树变矮，好减少磁盘操作。
B 树的每个节点是一个索引条目（例如：一个 <订单 ID，序号> 的组合），如果是行数据库可以索引到一条存储在磁盘上的记录。
继承 B 树：B+ 树
为了达到最高的效率，实战中我们往往使用的是一种继承于 B 树设计的结构，称为 B+ 树。B+ 树只有叶子节点才映射数据，下图中是对 B 树设计的一种改进，节点 1 为冗余节点，它不存储数据，只划定子树数据的范围。你可以看到节点 1 的索引 Key：12 和 30，在节点 3 和 4 中也有一份。