高频面试题：什么是B树？为啥文件索引要用B树而不用二叉查找树？

爱被打了一巴掌 2023-07-08 02:46 31阅读 0赞

面试官：你知道文件索引、数据库索引一般用什么数据结构来存储吗？

小秋：知道啊，一般都是用**树形结构**来存储的。

面试官：可以说说为啥用树形结构来存储吗？

小秋：树形结构例如想 B 树，B+ 树，二叉查找树都是有序的，所以查询效率很高，可以再 O(logn) 的时间复杂度查找到目标数据。

面试官：那可以问问文件索引，例如数据库索引一般用哪种树形结构吗？

小秋：大部分用 B+ 树，少部分用 B 树。（B和B+树太他么复杂了，幸好背了下面试题，嘻嘻）

面试官：想问下为什么要用 B 树而不用二叉查找树啊？或者为啥不用哈希表啊？哈希表的查找速度也很快呀。

小秋：哈希表虽然能够再 O(1) 查找到目标数据，不过如果我们要进行**模糊查找**的话，却只能遍历所有数据，并且如果出现了极端情况，哈希表冲突的元素太多，也会导致线性时间的查找效率的。

面试官：那为啥不用二叉查找树呢？

小秋：这个…..其实我也不知道，当时是在某个面试题中看到的答案的，嘻嘻。

面试官：那你可以回去等通知了….

### 二、为啥不用二叉查找树呢？ ###

小秋被怼后有点沮丧，跑过来问帅地关于 B 树的一些知识以及心中的疑问。

小秋：今天去面试，面试问我，为啥文件索引要用 B 树而不用二叉查找树，然后我想了下，感觉如果这是一颗比较平衡的二叉查找树的话，那么查找效率是非常快的，难度 B 树还能比它更快吗？

帅地：确实，如果是查找效率（即比较次数）的话，实际上二叉树可以说是最快的了，但是，我们的文件索引是存放在**磁盘**上的，所以我们不仅要考虑查找效率，还要考虑**磁盘的寻址加载次数**哦，而这也是我们为什么要用 B 树的原因。

小秋：难道二叉查找树会导致磁盘的加载次数更多吗？可以给我详细讲讲吗？

帅地：可以呀，不过听懂了，觉得我讲的不错，你要记得给我**多点赞，转发**哦。

小秋：绝对没问题。

### 三、什么是 B 树？ ###

帅地：要讲懂这个问题，我们先来了解一下什么是 B 树，其实，B 树和二叉查找树一样，都是**树**，**B 树**相当于是一棵**多叉查找树**，对于一棵 m 阶的 B 树具有如下特性：

1、根节点至少有两个孩子。

2、每个中间节点都包含 k - 1 个元素和 k 个孩子，其中 m/2 <= k <= m。

3、每一个叶子节点都包含 k - 1 个元素，其中 m/2 <= k <= m。

4、所有的叶子节点都位于同一侧。

5、每个节点中的元素从小到大排列，节点当中的 k - 1 个元素正好是 k 个孩子包含的元素的值域划分。

小秋：我去，这么复杂，鬼才记得住，我还是选择不学了，呜呜。

帅地：你别着急，这些规则我也记不住，只是让你大致知道一些这些规则，一般情况下，我们并不需要把它的规则完全背起来滴。为了加深理解，我给你举个 B 树的例子吧。例如：

![format_png][]

图中是一棵m = 3 的 3 阶 B 树，可以看出，树中有些节点是有**多个元素**的，并且和二叉查找树一样，左节点的所有元素的值都比父亲元素小。例如对于(3, 7)这个节点。两个元素把这个节点分割成**三个值域**，即可以有 3 个孩子。2 相当于 3 的左孩子节点，而 （4，6）相当于 3 的右孩子，同时也是 7 的左孩子，而 9 是 7 的右孩子。

和二叉查找树还是很相似滴，都是有序，且左孩子小，右孩子大，只是 B 树的一个节点可以有**多个元素**，并且有多个分支。而这些分支以及元素的数量规则，可以从上面的五个规则中查找哈。说实话，我也懒的记那些规则，只知道个大概以及 B 树的应用即可。

> 文章来源于微信公众：『苦逼的码农』，更多文章可搜索关注

### 四、小秋的疑惑 ###

小秋：我知道了，不过这种多叉的树，真的可以比二叉查找树效率更好吗，我怎么觉得不可以呢？

帅地：那你可以说说哦。

小秋：例如，上面的 B 树有 11 个元素，按照这 11 个元素，我们建立一个如下的二叉查找树，如图（我去，这个图片了好长时间，ppt 画的）

![format_png 1][]

**下面我们来进行查询效率比较**

**1、在 B 树中的查找次数**。  
现在假如我们要查询元素 9,对于 B 树，我们需要进行**4次比较**，例如：  
第一次比较：10 比较，比 10 小，所以再 10 的左孩子找。

![format_png 2][]

第二、三次比较：和 3 比较，比 3 大，这个时候我们还得和 7 比较。

![format_png 3][]

第四次比较：和 9 比较，相等，找到目标树，返回。

![format_png 4][]

所以最终的结果需要 4 次比较。

**2、在二叉树的比较结果**

为了节省篇幅，我就不逐个比较了，相信你也一眼就看出来了，也是需要 4 次比较。如图

![format_png 5][]

小秋：同样都是四次比较，而且，B 树的每一个节点，如果存放的元素比较多，那么 B 树的比较次数会更多，为什么就说 B 的效率比 二叉查找树快呢？

### 五、解决疑惑 ###

帅地：确实，如果单单从比较次数看的话，二叉查找树确实不比 B 树差，不过你忽略了一个很重要的点，那就是**磁盘的寻址加载次数**。

我们知道，在把磁盘里的数据加载到内存中的时候，是以**页**为单位来加载的，而我们也知道，**节点与节点之间的数据是不连续的**，所以不同的节点，很有可能分布在不同的**磁盘页**中。所以对于上面的二叉查找树，我们可能需要进行 4 次寻址加载，如图：

![format_png 6][]

而对于 B 树，由于 B 树的每一个节点，可以存放多个元素，所以磁盘寻址加载的次数会比较少，例如上面的例子中，用 B 树的话，只需要加载 3 次，如图：

![format_png 7][]

我们都知道，在内存的运算速度是非常快的，至少比磁盘的寻址加载速度，快了几百倍，而我们进行数值比较的时候，是在内存中进行的，虽然 B 树的比较次数可能比二叉查找树多，但是磁盘操作次数少，所以总体来说，还是 B 树快的多，这也是为什么我们用使用 B 树来存储的原因。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUUzWjRTVVR4ME1oYlUwVkxZM0tJRzVwdTlQYUdCVTBkbGpYd0o3czkySWxxdVhjYmljbWRyZGRRLzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUVRZlhGdmM0NmNBT2JlSkJzZjE5NjFiaHhJUDltcjdpY2lic09oRWRUTG9tQmt1Rm92c2lhYzJ3aWNnLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUVrTE9EOUk4Wk5IY3c0RkZnaWJjN1VKSzR6b2VpYXhhVWhqZG1Mc2lhTGVHekJVT2lhdURlZmZqaldBLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUV1WDlOMVFXY3FWRWVwYldYNXNLOGx1UWFWNTFUMEUzVVNnbzhueFk5MGliU0FrbzBpYWFCRjV6dy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUU3V21MQm5Palp6S2ljOFdrazh2TDNYVkhLYWlhSDhUUzdyOHNPRWJzcVRrUXhKR1FNaWNsa0JVZGcvNjQw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUVidU15dWNSSHZ1a2UyaWIzZ1ZVUjU1OVpTR25jWk9UanM1NWljQ2hISDRpY1FVVmY5YTZYam5UV1EvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUVwWWtwQ29laWFacm51eXhheHFVQXdWZDljOHMxWG5BN3lIaWFFVklOdWE0MVZSMVhRUXZWWURQdy82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9iOTVRSFBrY09NRDZEeWliMlgwUFJCSkZRb0xRWUUzRUVGNGNQY3IydnhkRXFpYWZ6cHpLQzVkNHVSTkE1UG5GbE1BTEZWQzdWeXRvWmliRWo5SGwyT0lFZy82NDA?x-oss-process=image/format,png