06 | 数据库检索：如何使用B+树对海量磁盘数据建立索引？

作者回复: b+树的叶子节点存的是什么?是位置还是具体数据？这个问题很好！你如果注意的话，会发现我文中有写“位置或数据”。事实上，两种方案都可以，而且这是两种数据库b+树的实现方案。只存数据的，是innoDB，而存文件位置的，是myIsam。这两种方案的各种特性根源都和b+树叶子节点存什么密切相关。你有兴趣可以去深入学习。 至于你的ipv4和ipv6的检索问题，其实你们之前ipv4的检索方案，是将ipv4直接作为数组下标查询，时间代价O(1)。和位图是不是很像? 那我提供三个思路你看看。 1.直接使用哈希表解决ipv6问题。时间代价也是o(1)，只是哈希表空间需要足够。 2.类似ipv4的位图思路，生成一个超大的位图，内存放不下的话，可以使用分布式技术，不同Redis存不同的分段。 3.参考roaring bitmap的思路(或者是倒排索引的思路)对大位图进行压缩处理。我们可以将ipv6分为4段。第一段就是32位，你可以沿用ipv4的处理思路，用位图法判断一个ipv6地址属于哪个位置，然后这个位置后面，再拿出下一段的32位，再做一个位图(其实就是分层位图)。然后你可以看看，哪些位图是可以替换为有序数组的。这样的设计就是空间可以压缩，但是查找效率会介于二分查找和o(1)之间。

作者回复: 很正确！这和Redis的范围查找也是使用遍历的方式是一个道理。取决于连续存储和不连续存储空间的差异。 再补充一个小细节，叶子节点往往是存在于磁盘中，不过由于叶子节点会分裂和合并，因此在磁盘中它们也不是连续的。

作者回复: 是的。其实这篇文章的开头，就分析了磁盘的特性:随机写的性能是最差的。因此，如果大量插入数据是写到磁盘中的话，那么就要尽量避免数据是随机写入的。 如果数据是存入b+树的话，正如你的分析，key太随机的话，就可能会导致不停地分裂节点，不过这只是一方面。更重要的另一方面，是b+树在具体的实现中，其实也会使用缓存技术，在内存中多次修改好叶子节点，再一次写回磁盘。如果数据是连续的话，那很可能会多个数据都在一个叶子节点上修改，修改完后只写一次磁盘，这样只有一次磁盘IO。但如果是随机的数据的话，那多个叶子节点就会被不停地读入内存-修改-写入磁盘，然后再读入内存-修改-写入磁盘。。。这样显然会造成多次磁盘IO，性能会大幅下降。

作者回复: 由于篇幅关系，我跳过了b树，只介绍和比较了b+树和lsm树。那么在这里我简单补充一下b树和b+树的区别和适用场景。 b树和b+树相比，有最核心的两个区别: 1.b树没有内部节点和叶子节点的区分，它的每个节点，都是即存key，又存了data。 2.由于没有内部节点和叶子节点的区分，使得b树没有将所有叶子节点用链表串联起来的结构。 这两个区别，会带来b树的两个检索特点: 1.进行单个key查询时，b树最快可以在o(1)的时间代价内就查到。而从平均时间代价来看，会比b+树稍快一些。但波动会比较大(因为每个节点即存key又存data，会使得树变高，底层的节点的io次数会变多)。 2.进行范围查询时，由于缺乏简单的叶子节点链接，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的io问题，效率不如b+树。 因此，存在大量范围检索的场景，适合使用b+树(比如数据库);而对于大量的单个key查询的场景，可以考虑b树(比如nosql的MongoDB)。

作者回复: 这是个好的学习习惯！你会发现，这篇写b+树的文章内容可能和你之前学习过的不一样。 我会从磁盘特性出发，结合索引与数据分离的设计思想和你解释b+树的来龙去脉。 学习b+树不是目的，而是一个学习“磁盘上的数据和索引应该如何处理”的过程。毕竟大数据时代，数据的存储和检索往往都要和磁盘打交道，数据库，日志系统，搜索引擎等都要解决这个问题。

作者回复: 是的。相信你看完加餐和这一篇以后，会发现许多高级数据结构就是基础篇的灵活组合应用。这样一步一步学习，我相信能帮助你更轻松和扎实地掌握相关知识。 关于思考题，你提到了很重要的一点:磁盘顺序访问效率很高。这其实和内存局部性原理的本质是一致的。 不过，b+树的叶子节点并不是在磁盘上连续存储的，由于它会不停分裂和合并，因此在物理存储上是零散的。（下一节课你会看到磁盘的局部性原理）。 b+树之所以范围查找采用顺序遍历，是因为它要将每个叶子节点依次读入内存处理。那既然遍历每个叶子节点是无法避免的，那我们就不需要额外计算一次y在哪个叶子节点了。 而内存中的有序数组不一样，它能将内存中连续数据成片拷贝出来，这会比遍历每个数组元素快很多。因此有序数组可以用两次二分查找定位x和y。

作者回复: 你补充了很重要的一点:一次IO代价远远大于内存中的多次条件判断。这也是我们文中说的尽可能减少磁盘访问次数的原则。寻找一次y所在的位置，即便内部节点都在内存中，但要到磁盘中的叶子节点中查找依然会带来一次IO，这个代价是可以避免的。

作者回复: 你说得很好。实际上，原始的b+树在真正工程使用时，会有许多问题，因此MySQL进行了许多优化。包括你说的page directory结构。还包括其实MySQL中的b+树也会使用wal技术等。

作者回复: 讨论区就是各种思想碰撞的地方，说出你的想法和疑惑，不仅能帮助自己理解得更清楚，也能帮助其他同学去对比和思考。 你的这个方案是分别找到min和max，然后用链表找出来所有元素。那你可以想一个细节，就是范围查找要将所有符合条件的元素返回。那么，所有符合条件的元素要怎么复制返回呢？ 在b+树中，即使我们知道了min和max所在的叶子节点，我们要获得所有符合条件的元素，也必须从min开始，沿着链表，将叶子节点一个一个读入内存进行处理。因此，既然遍历叶子节点的这一步无法避免，那么其实就不需要额外再计算一次max所在的叶子节点了。 而为什么有序数组可以用两次二分查找呢？是因为它找到了min和max以后，可以将中间连续数据进行成片的拷贝处理，效率会比一个元素一个元素遍历更高。

作者回复: 1.其实“维持树形结构的指针”，记录的就是下一个block的地址。因此通过这个指针就可以访问下一个block了。 2.关于联合索引到底长什么样子?其实并不神秘，它依然是保存了key和指针，只是这个key是一个组合key，要同时包含多个列的key的值。 举个例子，假设有两个列col1和col2做联合索引，col1的值是a，b，c，而col2的值是1，2，3。那么组合起来，在叶子节点就会有a1，a2，a3，b1，b2，b3，c1，c2，c3这九个组合key。每个key下面会带一个具体数据的地址，因此，{a1，地址}这就是一个完整的记录。再拆开，其实就是{a，1，地址}。 同理，中间节点也一样。比如说，一个中间节点的key是a1，b2，c2。那么，如果我们查询的组合key是a2，那么它位于a1和b2之间，我们就应该把这个中间节点a1这个key对应的指针取出，读出下一个block。因此，中间节点的结构也是{组合key，地址}，将组合key拆开，其实就是{col1-key，col2-key，地址}。这就是中间节点的数组中的一个元素。