你好，我是陈东。
在基础篇中，我们学习了许多和检索相关的数据结构和技术。但是在大规模的数据环境下，这些技术的应用往往会遇到一些问题，比如说，无法将数据全部加载进内存。再比如说，无法支持索引的高效实时更新。而且，对于复杂的系统和业务场景，我们往往需要对基础的检索技术进行组合和升级。这就需要我们对实际的业务问题和解决方案十分了解。
所以，从这一讲开始，我会和你一起探讨实际工作中的系统和业务问题，分享给你一些工业界中常见的解决方案，帮助你积累对应的行业经验，让你能够解决工作中的检索难题。
在工业界中，我们经常会遇到的一个问题，许多系统要处理的数据量非常庞大，数据无法全部存储在内存中，需要借助磁盘完成存储和检索。我们熟悉的关系型数据库，比如MySQL和Oracle，就是这样的典型系统。
数据库中支持多种索引方式，比如，哈希索引、全文索引和B+树索引，其中B+树索引是使用最频繁的类型。因此，今天我们就一起来聊一聊磁盘上的数据检索有什么特点，以及为什么B+树能对磁盘上的大规模数据进行高效索引。
磁盘和内存中数据的读写效率有什么不同？
首先，我们来探讨一下，存储在内存中和磁盘中的数据，在检索效率方面有什么不同。
内存是半导体元件。对于内存而言，只要给出了内存地址，我们就可以直接访问该地址取出数据。这个过程具有高效的随机访问特性，因此内存也叫随机访问存储器（Random Access Memory，即RAM）。内存的访问速度很快，但是价格相对较昂贵，因此一般的计算机内存空间都相对较小。
而磁盘是机械器件。磁盘访问数据时，需要等磁盘盘片旋转到磁头下，才能读取相应的数据。尽管磁盘的旋转速度很快，但是和内存的随机访问相比，性能差距非常大。到底有多大呢？一般来说，如果是随机读写，会有10万到100万倍左右的差距。但如果是顺序访问大批量数据的话，磁盘的性能和内存就是一个数量级的。为什么会这样呢？这和磁盘的读写原理有关。那具体是怎么回事呢？
磁盘的最小读写单位是扇区，较早期的磁盘一个扇区是512字节。随着磁盘技术的发展，目前常见的磁盘扇区是4K个字节。操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block），也叫作簇（Cluster）。当我们要从磁盘中读取一个数据时，操作系统会一次性将整个块都读出来。因此，对于大批量的顺序读写来说，磁盘的效率会比随机读写高许多。
现在你已经了解磁盘的特点了，那我们就可以来看一下，如果使用之前学过的检索技术来检索磁盘中的数据，检索效率会是怎样的呢？
假设有一个有序数组存储在硬盘中，如果它足够大，那么它会存储在多个块中。当我们要对这个数组使用二分查找时，需要先找到中间元素所在的块，将这个块从磁盘中读到内存里，然后在内存中进行二分查找。如果下一步要读的元素在其他块中，则需要再将相应块从磁盘中读入内存。直到查询结束，这个过程可能会多次访问磁盘。我们可以看到，这样的检索性能非常低。
由于磁盘相对于内存而言访问速度实在太慢，因此，对于磁盘上数据的高效检索，我们有一个极其重要的原则：对磁盘的访问次数要尽可能的少！
那问题来了，我们应该如何减少磁盘的访问次数呢？将索引和数据分离就是一种常见的设计思路。
如何将索引和数据分离？
我们以查询用户信息为例。我们知道，一个系统中的用户信息非常多，除了有唯一标识的ID以外，还有名字、邮箱、手机、兴趣爱好以及文章列表等各种信息。一个保存了所有用户信息的数组往往非常大，无法全部放在内存中，因此我们会将它存储在磁盘中。
当我们以用户的ID进行检索时，这个检索过程其实并不需要读取存储用户的具体信息。因此，我们可以生成一个只用于检索的有序索引数组。数组中的每个元素存两个值，一个是用户ID，另一个是这个用户信息在磁盘上的位置，那么这个数组的空间就会很小，也就可以放入内存中了。这种用有序数组做索引的方法，叫作线性索引（Linear Index）。
在数据频繁变化的场景中，有序数组并不是一个最好的选择，二叉检索树或者哈希表往往更有普适性。但是，哈希表由于缺乏范围检索的能力，在一些场合也不适用。因此，二叉检索树这种树形结构是许多常见检索系统的实施方案。那么，上图中的线性索引结构，就变成下图这个样子。
尽管二叉检索树可以解决数据动态修改的问题，但在索引数据很大的情况下，依然会有数据无法完全加载到内存中。这种情况我们应该怎么办呢？
一个很自然的思路，就是将索引数据也存在磁盘中。那如果是树形索引，我们应该将哪些节点存入磁盘，又要如何从磁盘中读出这些数据进行检索呢？你可以先想一想，然后我们一起来看看业界常用的解决方案B+树是怎么做的。
如何理解B+树的数据结构？
B+树是检索技术中非常重要的一个部分。这是为什么呢？因为B+树给出了将树形索引的所有节点都存在磁盘上的高效检索方案，使得索引技术摆脱了内存空间的限制，得到了广泛的应用。
前面我们讲了，操作系统对磁盘数据的访问是以块为单位的。因此，如果我们想将树型索引的一个节点从磁盘中读出，即使该节点的数据量很小（比如说只有几个字节），但磁盘依然会将整个块的数据全部读出来，而不是只读这一小部分数据，这会让有效读取效率很低。B+树的一个关键设计，就是让一个节点的大小等于一个块的大小。节点内存储的数据，不是一个元素，而是一个可以装m个元素的有序数组。这样一来，我们就可以将磁盘一次读取的数据全部利用起来，使得读取效率最大化。
B+树还有另一个设计，就是将所有的节点分为内部节点和叶子节点。尽管内部节点和叶子节点的数据结构是一样的，但存储的内容是不同的。
内部节点仅存储key和维持树形结构的指针，并不存储key对应的数据（无论是具体数据还是文件位置信息）。这样内部节点就能存储更多的索引数据，我们也就可以使用最少的内部节点，将所有数据组织起来了。而叶子节点仅存储key和对应数据，不存储维持树形结构的指针。通过这样的设计，B+树就能做到节点的空间利用率最大化。
此外，B+树还将同一层的所有节点串成了有序的双向链表，这样一来，B+树就同时具备了良好的范围查询能力和灵活调整的能力了。
因此，B+树是一棵完全平衡的m阶多叉树。所谓的m阶，指的是每个节点最多有m个子节点，并且每个节点里都存了一个紧凑的可包含m个元素的数组。
B+树是如何检索的？
这样的结构，使得B+树可以作为一个完整的文件全部存储在磁盘中。当从根节点开始查询时，通过一次磁盘访问，我们就能将文件中的根节点这个数据块读出，然后在根节点的有序数组中进行二分查找。
具体的查找过程是这样的：我们先确认要寻找的查询值，位于数组中哪两个相邻元素中间，然后我们将第一个元素对应的指针读出，获得下一个block的位置。读出下一个block的节点数据后，我们再对它进行同样处理。这样，B+树会逐层访问内部节点，直到读出叶子节点。对于叶子节点中的数组，直接使用二分查找算法，我们就可以判断查找的元素是否存在。如果存在，我们就可以得到该查询值对应的存储数据。如果这个数据是详细信息的位置指针，那我们还需要再访问磁盘一次，将详细信息读出。
我们前面说了，B+树是一棵完全平衡的m阶多叉树。所以，B+树的一个节点就能存储一个包含m个元素的数组，这样的话，一个只有2到4层的B+树，就能索引数量级非常大的数据了，因此B+树的层数往往很矮。比如说，一个4K的节点的内部可以存储400个元素，那么一个4层的B+树最多能存储400^4，也就是256亿个元素。
不过，因为B+树只有4层，这就意味着我们最多只需要读取4次磁盘就能到达叶子节点。并且，我们还可以通过将上面几层的内部节点全部读入内存的方式，来降低磁盘读取的次数。
比如说，对于一个4层的B+树，每个节点大小为4K，那么第一层根节点就是4K，第二层最多有400个节点，一共就是1.6M；第三层最多有400^2，也就是160000个节点，一共就是640M。对于现在常见的计算机来说，前三层的内部节点其实都可以存储在内存中，只有第四层的叶子节点才需要存储在磁盘中。这样一来，我们就只需要读取一次磁盘即可。这也是为什么，B+树要将内部节点和叶子节点区分开的原因。通过这种只让内部节点存储索引数据的设计，我们就能更容易地把内部节点全部加载到内存中了。
B+树是如何动态调整的？
现在，你已经知道B+树的结构和原理了。那B+树在“新增节点”和“删除节点”这样的动态变化场景中，又是怎么操作的呢？接下来，让我们一起来看一下。
首先，我们来看插入数据。由于具体的数据都是存储在叶子节点上的，因此，数据的插入也是从叶子节点开始的。以一个节点有3个元素的B+树为例，如果我们要插入一个ID=6的节点，首先要查询到对应的叶子节点。如果叶子节点的数组未满，那么直接将该元素插入数组即可。具体过程如下图所示：
如果我们插入的是ID=10的节点呢？按之前的逻辑，我们应该插入到ID 9后面，但是ID 9所在的这个节点已经存满了3个节点，无法继续存入了。因此，我们需要将该叶子节点分裂。分裂的逻辑就是生成一个新节点，并将数据在两个节点中平分。
叶子节点分裂完成以后，上一层的内部节点也需要修改。但如果上一层的父节点也是满的，那么上一层的父节点也需要分裂。
内部节点调整好了，下一步我们就要调整根节点了。由于根节点未满，因此我们不需要分裂，直接修改即可。
删除数据也类似，如果节点数组较满，直接删除；如果删除后数组有一半以上的空间为空，那为了提高节点的空间利用率，该节点需要将左右两边兄弟节点的元素转移过来。可以成功转移的条件是，元素转移后该节点及其兄弟节点的空间必须都能维持在半满以上。如果无法满足这个条件，就说明兄弟节点其实也足够空闲，那我们直接将该节点的元素并入兄弟节点，然后删除该节点即可。
重点回顾
好了，今天的内容就先讲到这里。你会发现，即使是复杂的B+树，我们将它拆解开来，其实也是由简单的数组、链表和树组成的，而且B+树的检索过程其实也是二分查找。因此，如果B+树完全加载在内存中的话，它的检索效率其实并不会比有序数组或者二叉检索树更高，也还是二分查找的log(n)的效率。并且，它还比数组和二叉检索树更加复杂，还会带来额外的开销。
但是，B+树最大的优点在于，它提供了将索引数据存在磁盘中，以及高效检索的方案。这让检索技术摆脱了内存的限制，得到了更广泛地使用。
另外，这一节还有一个很重要的设计思想需要你掌握，那就是将索引和数据分离。通过这样的方式，我们能将索引的数组大小保持在一个较小的范围内，让它能加载在内存中。在许多大规模系统中，都是使用这个设计思想来精简索引的。而且，B+树的内部节点和叶子节点的区分，其实也是索引和数据分离的一次实践。
课堂讨论
最后，咱们来看一道讨论题。
B+树有一个很大的优势，就是适合做范围查询。如果我们要检索值在x到y之间的所有元素，你会怎么操作呢？
欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这篇文章分享给你的朋友。
精选留言
2020-04-09 08:18:28
内存是半导体元件，访问速度快，可以直接根据地址读取数据
磁盘是机械器件，在读取数据时需要移动磁盘进行寻址，这个过程比较慢。所以在随机读写方面，磁盘远远慢于内存。但磁盘也有它的特点，磁盘最小读写单位是扇区，而操作系统的最小读写单位是块(块往往是多个扇区的组合)，正是因为这种特性，使得磁盘的顺序读写性能远高于随机读写。
所以，要想在磁盘中实现高效检索的重要原则是:对磁盘的访问次数尽可能少
2.有效减少磁盘访问次数的思路是将索引和数据分离
因为高效检索的原则是减少对磁盘的访问，对于数据量比较小的情况，可以直接把磁盘中的数据加载到内存中，可以利用内存的局部性原理加快检索。但现实往往是数据量非常大，所以我们还是需要借助磁盘来存储数据。访问磁盘必不可少，但可以通过将索引和数据分离的办法来减少对磁盘的访问。
将索引和数据分离的初衷是把索引存到内存中，数据存到磁盘中。索引可以有三种方案:
①线性索引，比如用数组存放。但数组在数据频繁变更的场景下不适合，因为数组更新涉及到大量数据的移动
②哈希索引，缺乏范围检索能力，适用场景有限
③树形索引，比如用二叉检索树，既支持范围检索，又能保证数据频繁更新的情况下数据移动数量少，所以具有普适性。
即使二叉检索树实现所以有诸多好处，但也避免不了数据量太大的情况不能完全加载到内存中的这种情况，所以只能将索引数据也存到磁盘中。
3.b+树的设计
b+树是一棵完全平衡的 m 阶多叉树。m 阶表示每个节点最多有 m 个子节点，并且每个节点存的是一个可以容纳 m 个元素的紧凑数组。所以一般 b+ 树比较矮，2-4层的 b+ 树就能存储非常大的数据量了。
b+树有几个设计思想:
①让一个节点的大小等于一个块的大小，节点内存储可以装下多个元素的有序数组。这样就可以充分利用操作系统按块读取的特性，使得读取效率最大化。
②将节点区分为内部节点和叶子节点。他们结构相同，但存储的内容不同。
内部节点存储 key 和维持树形结构的指针
叶子节点存储 key 和数据
这么做可以使得内部节点存储更多的索引数据。
③所有节点通过双向链表串联
可以方便范围查询，这样的做法也有点跳表的意思。
b+树如何检索？
先从磁盘加载根节点所在的块，然后通过二分查找要检索的数据在数组中哪两个相邻元素中间，然后不断读取块，直到读到叶子节点，有了叶子节点就可以在叶子节点的数组中通过二分查找要检索的数据对应的指针。然后通过指针读取磁盘获取数据。
【如果内存空间比较充足，可以把内部节点全部加载到内存中，以减少读取磁盘的次数】
b+树如何动态调整？
再添加数据和删除数据时，b+ 树为了保证平衡可能会进行页分裂和页合并【正是由于存在页分裂和页合并，所以叶子节点在磁盘上并不是连续存储的】
4.思考题
B+ 树有一个很大的优势，就是适合做范围查询。如果我们要检索值在 x 到 y 之间的所有元素，你会怎么操作呢？
先查找 x 元素对应的叶子节点，然后往后遍历直到大于 y 元素停止
5.疑惑
我记得 MySQL b+树索引的叶子节点存储的是数据，老师在专栏中介绍存储的是元素的位置信息，这里有些疑惑，还请老师指点一下。
6.问题请教
这个问题也和检索相关，但可能和今天的主题没啥关系
我们 DSP 这边需要对 ADX 请求过来的数据解析判断，现在 ipv6 的数据多了，我们想在调用内部 ip 定位服务前对这些数据进行缓存，key 对应 ipv6 地址，value 是 ip 对应的内部 localId，还要有过期时间。这里可以考虑放 redis 中，但我们想有没有其他好的方案。我同事做了一个对 ipv4 不错的缓存方案，因为 ipv4 都是数字，我们内部认为前三位相同就对应同一个 localId，他采用 long 类型的三维数组来存储，三位数组的下标对应 ipv4 的前三个数字，数组对应的值是 localId || cacheTime << 32 的值，即用一个 long 型的高 32 位存缓存时间，低32位存 localId，这个方案性能很好。但 ipv6 不止数字，这个方案套不进去，调研了一些，有说使用 Trie 树来做，但我看 Trie 树的应用场景是判断字符串是否存在，我们这个场景好像用不上或我没想到用的办法，还请老师指点一下，用什么样的检索方法实现 ipv6 达到类似 ipv4 那样的功能。
2020-04-08 11:34:17
2020-05-10 06:40:55
2020-05-30 14:51:35
2020-04-08 08:37:53
2020-04-08 12:42:21
2020-04-08 11:00:17
我一个非计算专业的都可以听得很明白。
其实，各种高级的算法和数据结构，都是在不同的应用场景下，对最基础的数据结构和算法进行的组合。所以说，基本功很重要！
对于最后的思考题：
先通过内部节点找到x，继而找到叶子节点对应的元素，顺序读写对于硬盘来讲效率并不低，所以顺序遍历叶子节点找到y结束检索。
之所以硬盘顺序读写效率不低，是因为数据从硬盘读取到内存的时候是按块读取的，在内存中检索的时候可以复用读取的块内容。
我之前读资料看到，cpu缓存的局部性原理，【对于硬盘的按块读取，这个算不算局部性原理呀？】
2020-05-06 17:11:49
如果元素频繁更新，采用有序数组不是个好主意，至少mysql用的是单向链表 + page directory。
单向链表是为了遍历查询。
page dirctory则是一个数组，记录第N*M个元素的page offset，当执行kv查询时，借助page directory对节点页内的单向链表实现二分查找。
2020-04-08 09:38:42
1. 只有叶子节点存储数据
2. 一个节点上存储的是一组数据, 数组存储
3. 同一层的节点之间用双向链表串在一起
这样的话、我觉得范围查询时、可以先找到 min 所在的叶子节点位置、再找到max所在的叶子节点位置、min和max的查询效率很高、再利用同一层间的双向链表应该可以很快的找到所有元素 ?
----------
我也不知道对不对, 若有不对的地方、希望老师指正、别误导看到的同学~~~
2020-05-19 18:45:03
另外, 在读问答区的时候, 有个回复里说, 联合索引内部节点存储的是多列数组, 这里是每个数组存储一列吗 ?(PS: 假如A、B、C组成联合索引, 内部节点数组会是[[A], [B], [C]]还是 [A, B, C]) ？ 为什么呢 ? 猜想: 因为联合索引可以使用最左前缀, 应该是[[A],[B],[C]]保持多维度(A->B->C)有序 ?
2020-05-13 16:48:08
我也来提几个疑惑：
内部节点（除根节点/叶子节点）外，元素个数 count_e 与指针数 count_p 的关系，是 count_p= count_e ，还是count_p = count_e + 1 ?
比如说某个节点有元素 3,5，那么下面两个哪个才是正确？
指针方案一：p1<3, 3<=p2<5， 5<=p3
指针方案二：3<=p1<5, 5<=p2
提出这个问题是因为看了许多讲解B+树的，大家画的图都集中在这两个类型，是有点迷。
维护B+树过程中，节点元素过多，导致B+树变成“违规”状态，因此需要分裂，从叶子节点递归向树根分裂，在根节点已满的时候，如何处理根节点? wiki上说会“新建一个根节点”，那是否会改变树的阶数？
维护B+树过程中，节点元素过少，会导致B+树变成“违规”状态，因此需要转移或合并，如果合并，删除节点后，应该也要递归向树根检查？是否也会如上一个问题到达根节点，而产生新的根节点？
上述讲述维护B+树过程中，都有一个判断元素数量是否“半满”的条件，这个半满是否就是m阶B+树的 m/2, 那么这个值是如何推导出来的，或者说，如何证明半满是对m阶B+树最好的实现?
2020-04-08 10:02:36
2020-04-08 07:01:49
感谢老师的分享，又学到了好多👏，我之前写的就只是有序数组二分查找，是时候好好改造了😃
2020-05-07 16:01:21
2020-04-22 11:51:35
2.通过二分法查找到x后，直接链表遍历下一块的第一个数据与y数据比较大小，来找到范围。
不知这两种哪种是对的，还是都不对，看评论区都是遍历链表，感觉这种遍历链表只有一个数据。希望东哥可以解开我的疑惑？
2020-04-08 14:45:19
2020-04-08 08:47:08
1.数据容量过大的时候，内存无法一次性加载
2.内存的读写速度比磁盘有数量级上的优势，所以不能将数据全部放入磁盘（速度慢），也不能全部放入内存（资源昂贵）
B+:索引和数据分离，三层数结构。索引存入内存提高速度，数据存入磁盘提高存储容量。
数据架构:树+双向链表（树提供了二分查找的能力，双向链表提供了范围检锁的能力）
课后题:
1.先利用二分查找确定start的位置
2.然后向右测走step(y-x)步（如果每组叶子节点还记录了这组长度，实际更容易理解），至此确定了x-y的范围，可以读取对应的block，获得最终数据。
2024-02-06 15:30:06
2023-04-08 19:03:23
2023-03-23 15:06:20