柠檬少年|腾讯面试官用「B+树」虐哭我了( 二 ) 作者|L的存在来源|我是程序员小贱（ID

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

让节点大小等于块大小

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

内部节点与叶子节点

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

内部节点与叶子节点

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

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

m阶多叉树

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 。对于当前的计算机而言，我们完全可以将前面三层存放于内存中，只需要将第四层存放于磁盘中，这样我们只需要和磁盘打一次交道就分手，也就是面试想知道的为什么要分为内部节点与叶子节点。
B+树如何进行动态的调整上面介绍了B+树的结构和查询原理，现在我们看看B+树增加和删除是怎么个情况
现在我们以三个元素的B+树为例，假设目前我们要插入ID为6=5的元素，第一步先查找对应的叶子节点，如果叶子节点没有满，直接插入即可