数据结构 B 树概念详解

1. 常见的搜索结构

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景（内查找）。

2. 问题提出

如果数据量很大，比如有 100G 数据，无法一次放进内存中，那就只能放在磁盘上了。如果放在磁盘上，有时需要搜索某些数据，该如何处理？

我们可以考虑将关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，当通过搜索树找到要访问数据的关键字时，取这个关键字对应的地址去磁盘访问数据。

但是，实际中去查找的这个 key 可能不都是整型：可能是字符串比如身份证号码，那这时我们还把所有的 key 和对应数据的地址都存到内存，也可能是存不下的。

这时候可以做一个改动：不再存储 key，只存储地址。

那这样的话如何判断找到了呢？需要拿着当前的地址去访问磁盘进行判断。

比如现在要找 key 为 77 的这个数据，从根结点开始，首先访问根结点中的地址对应磁盘的数据，是 34，那 77 大于 34，所以往右子树找，右子树 0x77 对应的是 89（又一次访问磁盘），77 比 89 小，再去左子树找，左子树地址 0x56 访问磁盘对应的是 77 找到了。

这样做的问题是什么呢？最坏的情况下我们要进行高度次的查找，那就意味着要进行高度次的磁盘 IO。

如果我们使用红黑树或者 AVL 树的话，就是 O(log₂N) 次。那如果是在内存中的话，这个查找次数还是很快的，但是现在数据量比较大是在磁盘上存的，而磁盘的速度是很慢的。

使用平衡二叉树搜索树的缺陷 平衡二叉树搜索树的高度是 logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN 次的磁盘访问，是一个难以接受的结果。

使用哈希表的缺陷 哈希表的效率很高是 O(1)，但是一些极端场景下某个位置哈希冲突很严重，导致访问次数剧增，也是难以接受的。

那如何加速对数据的访问呢？

1. 提高 IO 的速度 (SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
2. 降低树的高度——多叉平衡树

B 树其实就是多叉平衡搜索树。

3. B 树的概念

1970 年，R.Bayer 和 E.mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树并且是绝对平衡，称为 B 树 (后面有一个 B 树的改进版本 B+ 树，然后有些地方的 B 树写的的是 B-树，注意不要误读成"B 减树")。

一棵 m 阶 (m>2) 的 B 树，是一棵 M 路的平衡搜索树，可以是空树或者满足以下性质的树：

1. m 阶 B 树的每个节点最多有 m 个分支（子树），m-1 个元素（关键字）。