腾讯面试官用「B+树」虐哭我了

桃扇骨 2022-12-08 14:21 166阅读 0赞

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

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

![会话1][1] 会话1  
![会话2][2] 会话2

--------------------

就问登哥傲娇不傲娇吧，回到正题，今天分享的几点如下

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

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

对于磁盘，属于**机械器件**。每当磁盘访问数据的时候，都需要等磁盘盘片**旋转**到磁头，才能读取相应的数据，即使磁盘的转速很快，但是和内存的随机访问相比还是渣渣。所见，如果是随机读写，其性能差距是非常大的。那如果是顺序访问大量数据的时候，磁盘的性能和内存其实差距就不大了，**这是为啥**？

磁盘的最小读写单位是**扇区**，现在磁盘扇区一般是4k个字节，对于操作系统，一次性会读取**多个扇区**，至此操作系统的最小读取单位就是**块**。每当我们从磁盘读取一个数据，操作系统就会一次性读取整个块，那么对于大量的顺序读写来说，磁盘效率会比随机读写高很多。

假设现在你有个有序数组，全部以块的方式存放在磁盘中，现在我们通过**二分查找**的方式查找元素A。首先我们找到中间元素，并从块中取出，将其从磁盘放入内存中，然后再内存中进行二分查找。在进行下一步的时候，如果查找的元素在其他块中，我们需要继续从磁盘读出到内存中。这样反反复复的从磁盘到内存，其效率将非常的低。所以我们需要想办法让访问磁盘的次数尽可能的低。

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

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

![用户数据][format_png 1] 用户数据

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

![有序数组][format_png 2] 有序数组

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

![在这里插入图片描述][format_png 3] 在这里插入图片描述

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

## 2 B+树 ##

*  让节点大小等于块大小

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

*  内部节点与叶子节点

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

![内部节点与叶子节点][format_png 4] 内部节点与叶子节点

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

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

![m阶多叉树][m] m阶多叉树

## 3 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。对于当前的计算机而言，我们完全可以将前面三层存放于内存中，只需要将第四层存放于磁盘中，这样我们只需要和磁盘打一次交道就分手，也就是面试想知道的**为什么要分为内部节点与叶子节点**。

## 4 B+树如何进行动态的调整 ##

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

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

![插入元素6][6] 插入元素6

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

![节点分裂][format_png 5] 节点分裂

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

![节点分裂][format_png 6] 节点分裂

**总结**

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

你的**点赞**和**在看**是我前进的动力，Thanks！

[1]: /images/20221123/eeb0fc49dd864a8e952eca9115140c31.png
[2]: /images/20221123/08c5fa3ddf2d4264a2e3093a114e9ca0.png
[format_png]: /images/20221123/54361a2ad9f94b8b89432ed83235b288.png
[format_png 1]: /images/20221123/e71f0b2a84384f22b7d721e9c9e9c018.png
[format_png 2]: /images/20221123/6ac224fc9c274a598586a61856cad010.png
[format_png 3]: /images/20221123/8cb8f6f10bbf4452ad3f935548bb29f5.png
[format_png 4]: /images/20221123/e6f37a46929543c689023133d8042a8e.png
[m]: /images/20221123/a317b691db8e4beda002583ac09703b8.png
[6]: /images/20221123/12d4497c6e6540cd91b0605e97100c41.png
[format_png 5]: /images/20221123/85681d6ec9594518a0a37e1828bc5374.png
[format_png 6]: /images/20221123/3735ddeda2c74e3c948d899d8598e535.png