06 | 数据库检索：如何使用B+树对海量磁盘数据建立索引？
讲述：陈东
时长:大小17.43M
磁盘和内存中数据的读写效率有什么不...
精选留言
每天晒白牙2020-04-091.磁盘和内存中数据读写效率的对比 内存是半导体元件，访问速度快，可以直接根据地址读取数据 磁盘是机械器件，在读取数据时需要移动磁盘进行寻址，这个过程比较慢。所以在随机读写方面，磁盘远远慢于内存。但磁盘也有它的特点，磁盘最小读写单位是扇区，而操作系统的最小读写单位是块(块往往是多个扇区的组合)，正是因为这种特性，使得磁盘的顺序读写性能远高于随机读写。 所以，要想在磁盘中实现高效检索的重要原则是:对磁盘的访问次数尽可能少 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 那样的功能。展开作者回复: 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)之间。
28
奕2020-04-08先通过二分查找找到 x 元素， 然后往后遍历叶子节点的链表（链表是有序的） 直至大于 y 停止，得到范围。 这里不能使用两次二分查找的原因是，叶子节点数据结构是链表，内存不是连续的，即使使用了2次二分查找找到了 x 和 y 还是要遍历链表得到这个范围的所有值的。 对于有序数组是可以的，因为内存是连续的作者回复: 很正确！这和Redis的范围查找也是使用遍历的方式是一个道理。取决于连续存储和不连续存储空间的差异。 再补充一个小细节，叶子节点往往是存在于磁盘中，不过由于叶子节点会分裂和合并，因此在磁盘中它们也不是连续的。
共 3 条评论24
Joe Black2020-05-10之前看过别的文章说，大量插入数据时，最好索引字段是有序的，尽量别是UUID这样完全随机的值。看了这篇课程，感觉是不是因为如果索引值太随机，会导致B+树很频繁的分裂节点呢？如果插入的时候有序，是不是性能更好？作者回复: 是的。其实这篇文章的开头，就分析了磁盘的特性:随机写的性能是最差的。因此，如果大量插入数据是写到磁盘中的话，那么就要尽量避免数据是随机写入的。 如果数据是存入b+树的话，正如你的分析，key太随机的话，就可能会导致不停地分裂节点，不过这只是一方面。更重要的另一方面，是b+树在具体的实现中，其实也会使用缓存技术，在内存中多次修改好叶子节点，再一次写回磁盘。如果数据是连续的话，那很可能会多个数据都在一个叶子节点上修改，修改完后只写一次磁盘，这样只有一次磁盘IO。但如果是随机的数据的话，那多个叶子节点就会被不停地读入内存-修改-写入磁盘，然后再读入内存-修改-写入磁盘。。。这样显然会造成多次磁盘IO，性能会大幅下降。
共 2 条评论16
青鸟飞鱼2020-05-30老师你好，b树、b+树都可以应用于关系数据库，而MongoDB作为非关系数据库，用的就是b树，而非LSM树，这几种树有什么应用场景吗？作者回复: 由于篇幅关系，我跳过了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)。
14
夜空中最亮的星2020-04-08今天的课需要听2遍作者回复: 这是个好的学习习惯！你会发现，这篇写b+树的文章内容可能和你之前学习过的不一样。 我会从磁盘特性出发，结合索引与数据分离的设计思想和你解释b+树的来龙去脉。 学习b+树不是目的，而是一个学习“磁盘上的数据和索引应该如何处理”的过程。毕竟大数据时代，数据的存储和检索往往都要和磁盘打交道，数据库，日志系统，搜索引擎等都要解决这个问题。
10
峰2020-04-08看到大家都倾向于说一次查找，然后条件遍历，出于的考虑是遍历是不可避免的。遍历虽然不可避免，但遍历每条数据的判断是可以避免的，所以这里取舍的点在于对每条数据判断和多一次查找，后者可能带来更大的io开销，而且tp场景数据量也不多，不会遍历太多块，最后就是传统tp数据库查询瓶颈在io延时而不是吞吐更不是cpu多几次条件判断上。作者回复: 你补充了很重要的一点:一次IO代价远远大于内存中的多次条件判断。这也是我们文中说的尽可能减少磁盘访问次数的原则。寻找一次y所在的位置，即便内部节点都在内存中，但要到磁盘中的叶子节点中查找依然会带来一次IO，这个代价是可以避免的。
共 2 条评论6
wangkx
2020-04-08感谢陈东哥，从计算机的组成原理到B+树，娓娓而谈，自己受益良多。 我一个非计算专业的都可以听得很明白。 其实，各种高级的算法和数据结构，都是在不同的应用场景下，对最基础的数据结构和算法进行的组合。所以说，基本功很重要！ 对于最后的思考题： 先通过内部节点找到x，继而找到叶子节点对应的元素，顺序读写对于硬盘来讲效率并不低，所以顺序遍历叶子节点找到y结束检索。 之所以硬盘顺序读写效率不低，是因为数据从硬盘读取到内存的时候是按块读取的，在内存中检索的时候可以复用读取的块内容。 我之前读资料看到，cpu缓存的局部性原理，【对于硬盘的按块读取，这个算不算局部性原理呀？】作者回复: 是的。相信你看完加餐和这一篇以后，会发现许多高级数据结构就是基础篇的灵活组合应用。这样一步一步学习，我相信能帮助你更轻松和扎实地掌握相关知识。 关于思考题，你提到了很重要的一点:磁盘顺序访问效率很高。这其实和内存局部性原理的本质是一致的。 不过，b+树的叶子节点并不是在磁盘上连续存储的，由于它会不停分裂和合并，因此在物理存储上是零散的。（下一节课你会看到磁盘的局部性原理）。 b+树之所以范围查找采用顺序遍历，是因为它要将每个叶子节点依次读入内存处理。那既然遍历每个叶子节点是无法避免的，那我们就不需要额外计算一次y在哪个叶子节点了。 而内存中的有序数组不一样，它能将内存中连续数据成片拷贝出来，这会比遍历每个数组元素快很多。因此有序数组可以用两次二分查找定位x和y。
共 2 条评论6
时隐时现2020-05-06"节点内存储的数据，不是一个元素，而是一个可以装 m 个元素的有序数组" 如果元素频繁更新，采用有序数组不是个好主意，至少mysql用的是单向链表 + page directory。 单向链表是为了遍历查询。 page dirctory则是一个数组，记录第N*M个元素的page offset，当执行kv查询时，借助page directory对节点页内的单向链表实现二分查找。作者回复: 你说得很好。实际上，原始的b+树在真正工程使用时，会有许多问题，因此MySQL进行了许多优化。包括你说的page directory结构。还包括其实MySQL中的b+树也会使用wal技术等。
4
牛牛2020-04-08B+树 1. 只有叶子节点存储数据 2. 一个节点上存储的是一组数据, 数组存储 3. 同一层的节点之间用双向链表串在一起 这样的话、我觉得范围查询时、可以先找到 min 所在的叶子节点位置、再找到max所在的叶子节点位置、min和max的查询效率很高、再利用同一层间的双向链表应该可以很快的找到所有元素 ? ---------- 我也不知道对不对, 若有不对的地方、希望老师指正、别误导看到的同学~~~作者回复: 讨论区就是各种思想碰撞的地方，说出你的想法和疑惑，不仅能帮助自己理解得更清楚，也能帮助其他同学去对比和思考。 你的这个方案是分别找到min和max，然后用链表找出来所有元素。那你可以想一个细节，就是范围查找要将所有符合条件的元素返回。那么，所有符合条件的元素要怎么复制返回呢？ 在b+树中，即使我们知道了min和max所在的叶子节点，我们要获得所有符合条件的元素，也必须从min开始，沿着链表，将叶子节点一个一个读入内存进行处理。因此，既然遍历叶子节点的这一步无法避免，那么其实就不需要额外再计算一次max所在的叶子节点了。 而为什么有序数组可以用两次二分查找呢？是因为它找到了min和max以后，可以将中间连续数据进行成片的拷贝处理，效率会比一个元素一个元素遍历更高。
共 3 条评论4- 牛牛2020-05-19又读了一遍, 有个疑问: 既然内部节点存储的只是key和维持树形结构的指针, 那么是怎么知道下一个block的位置的呢 ? 另外, 在读问答区的时候, 有个回复里说, 联合索引内部节点存储的是多列数组, 这里是每个数组存储一列吗 ?(PS: 假如A、B、C组成联合索引, 内部节点数组会是[[A], [B], [C]]还是 [A, B, C]) ？ 为什么呢 ? 猜想: 因为联合索引可以使用最左前缀, 应该是[[A],[B],[C]]保持多维度(A->B->C)有序 ?
作者回复: 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，地址}。这就是中间节点的数组中的一个元素。
3