# 【NO.318】腾讯面试官用「B+树」虐哭我了

我们知道当系统要处理的数据量非常庞大的时候，数据不可能全部存放于内存，需要借助磁盘来完成存储和检索。在数据库中支持很多种索引方式，常见有哈希索引、全文索引和B+树索引。今天将和大家分享使用B+树作为索引的优缺点。

面试很多互联网公司，都会问这个问题，也许我们看过太多面经内容，但是基本上答案千篇一律，对于面试官而言也是基本上听腻了，是多么希望能听到不一样的解答，那么今天希望这篇文章可以给你不一样的答案。

今天分享的几点如下：

![img](https://pic4.zhimg.com/80/v2-104c46a12f7b68d440530dc72551e65f_720w.webp)

## 1.**数据从磁盘读写与内存读写有哪些不同**

> 我们平时接触的有机械硬盘和固态硬盘。内存属于半导体器件，对于内存，我们知道内存地址就可以通过地址拿到数据，也就是内存的随机访问特性。访问速度快但是贵，所以内存空间一般比较小。

对于磁盘，属于机械器件。每当磁盘访问数据的时候，都需要等磁盘盘片旋转到磁头，才能读取相应的数据，即使磁盘的转速很快，但是和内存的随机访问相比还是渣渣。

所见，如果是随机读写，其性能差距是非常大的。那如果是顺序访问大量数据的时候，磁盘的性能和内存其实差距就不大了，这是为啥？

磁盘的最小读写单位是扇区，现在磁盘扇区一般是4k个字节，对于操作系统，一次性会读取多个扇区，至此操作系统的最小读取单位就是块。

每当我们从磁盘读取一个数据，操作系统就会一次性读取整个块，那么对于大量的顺序读写来说，磁盘效率会比随机读写高很多。

假设现在你有个有序数组，全部以块的方式存放在磁盘中，现在我们通过二分查找的方式查找元素A。首先我们找到中间元素，并从块中取出，将其从磁盘放入内存中，然后再内存中进行二分查找。

在进行下一步的时候，如果查找的元素在其他块中，我们需要继续从磁盘读出到内存中。这样反反复复的从磁盘到内存，其效率将非常的低。所以我们需要想办法让访问磁盘的次数尽可能的低。

## 2.**数据和索引分离**

> 我们以公安系统为例。系统中的用户非常多，每个用户除了姓名，年龄等基本信息外，当然还有一个唯一标识的ID，我们拿到这个ID，就可以知道对应的基本信息。但是每个用户的基本信息太多不可能全部存放在内存中，因此考虑存储于磁盘中。

![img](https://pic2.zhimg.com/80/v2-5ef83022526f59489d63ee51c0e1b9e9_720w.webp)

用户数据

- 采用有序数组的方式，其中分别存储用户ID和用户信息所在磁盘的位置，这样我只需要存放两个元素，直接存放于内存。如下图所示

![img](https://pic4.zhimg.com/80/v2-9347a157b74f20ec993e347482ddade3_720w.webp)

有序数组

但是在数据频繁变化的场景中，有序数组的弊端就出现了。大部分情况还是考虑使用二叉检索树或者哈希表的方式。但是哈希表又不支持区间查询，因此更多的使用二叉检索树的方式。如下图所示：

![img](https://pic3.zhimg.com/80/v2-6c050de8353d625b249050f1348077a6_720w.webp)

如果索引太多，依然不能完全存放于内存中，那我们是不是可以考虑将索引也存放于磁盘中？如何高效的在磁盘中组织索引的结构？这就引入了B+树。

## **3.B+树**

- 让节点大小等于块大小

> 我们知道操作系统在对磁盘进行访问的时候，通常是按照块的方式读取。如果当前你需要读取的数据只有几个字节，但是磁盘依然会将整个块读出来，这样子是不是读写效率就很低呢。在B+树中，大佬采用让一个节点大小等于一个块的大小，节点中存放的不是一个元素，而是一个有序的数组，这样充分利用操作系统的套路，使得读取效率的最大化

- 内部节点与叶子节点

> 内部节点和叶子节点虽然是一样的结构，但是其存储的内容有所区别。内部节点存放key以及维持树形结构的指针，它并不存放key对应的数据。而叶子节点存放key和对应的数据，不存放维持树形结构的指针，这样使得节点空间的利用最大化。

![img](https://pic2.zhimg.com/80/v2-d43f8d4acc9e1b450f2e5c8301fc9715_720w.webp)

内部节点与叶子节点

- B+树使用双向链表的方式，具有良好的范围查询能力和灵活的调整能力

综上三点，B+树是一颗完全平衡的m阶多叉树。

![img](https://pic2.zhimg.com/80/v2-e36a724c8884348d30cca34f25932129_720w.webp)

m阶多叉树

## 4.**B+树的检索方案**

> 刚才吹了一波B+树多么的牛逼，到底是怎么检索的？具体的查找过程是这样的：我们先确认要寻找的查询值，位于数组中哪两个相邻元素中间，然后我们将第一个元素对应的指针读出，获得下一个 block 的位置。读出下一个 block 的节点数据后，我们再对它进行同样处理。这样，B+ 树会逐层访问内部节点，直到读出叶子节点。对于叶子节点中的数组，直接使用二分查找算法，我们就可以判断查找的元素是否存在。如果存在，我们就可以得到该查询值对应的存储数据。如果这个数据是详细信息的位置指针，那我们还需要再访问磁盘一次，将详细信息读出。

B+树是一个m阶的多叉树，所以B+树中的一个节点可以存放m个元素的数组，ok，这样的话，只需要几层的b+树就可以索引数据量很大的数了。比如1个2k的节点可以存放200个元素，那么一个4层的B+树就能存放200^4，即16亿个元素。

如果只有四层，意味着我们最多访问磁盘4次，假设目前每个节点为2k，那么第一层就一个节点也就2k，第二层节点最多200个元素，一共就是0.8M。第三层200^2，也就是40000个节点，一共80M。对于当前的计算机而言，我们完全可以将前面三层存放于内存中，只需要将第四层存放于磁盘中，这样我们只需要和磁盘打一次交道就分手，也就是面试想知道的为什么要分为内部节点与叶子节点。

## 5.**B+树如何进行动态的调整**

> 上面介绍了B+树的结构和查询原理，现在我们看看B+树增加和删除是怎么个情况

现在我们以三个元素的B+树 为例，假设目前我们要插入ID为6=5的元素，第一步先查找对应的叶子节点，如果叶子节点没有满，直接插入即可

![img](https://pic1.zhimg.com/80/v2-47604db1871b26e7d2e78389652cc1e8_720w.webp)

插入元素6

如果我们插入的元素是10？按道理我们应该插入到9后面，但是节点已经满了，所以我们需要采取其他的方式。方法是将此叶子节点进行分裂，即生成一个新的节点，然后将数据在两个节点中平分。

![img](https://pic3.zhimg.com/80/v2-c076b04a6965196222b27532bf3aa23a_720w.webp)

节点分裂

很明显，叶子节点的分裂影响到了父节点，如果父节点也是满的，也要进行分裂

![img](https://pic4.zhimg.com/80/v2-6572b96960b4c930826f894f0a96153b_720w.webp)

节点分裂

## 6.**总结**

> 从大问题拆分为小问题并逐个解决是我们在生活学习重要的本领，比较复杂的B+树其实也就是基本的数据结构(数组，链表，树)组成，其检索过程实际上就是二分查找，所以如果B+树完全载入内存，它的检索效率和有序数组/二叉检索树差不多，但是却更加复杂。B+树最大的优点在于它将索引存放在磁盘，让检索技术摆脱了内存限制，另外通过将索引和数据分离的方式，将索引的数组大小保持在较小范围，这样精简索引。

原文地址：https://zhuanlan.zhihu.com/p/522591122

作者：Linux