块存储与 B 树:让一次读取带回更多索引¶
一次读盘可以带回多少分岔?¶
如果树的每个节点只放一个用于比较的值(键),每向下一层都可能再读一次盘。磁盘上的数据可以按一片连续空间一起读,这片空间叫**块**。如果一块能带回一组有序键,例如 20、50、80,一次读取就能在内存里分辨多个方向。查找 60,读到这一块后直接走 50 到 80 的范围;换来的是节点内搜索和更新时维护更多键。
键多到一个块也装不下时怎么办?
可以把挤满的树节点分成两个,并把用来告诉上层「比这个数大就走右边」的分隔键交给上一层。更新比较复杂,但较大的分叉数能减少许多查询的跨块读取。
先修:二叉搜索树。
读完能做:说明索引节点为什么常保存多个关键字,并辨认查找路径和换来的维护成本。
慢的是读一个块¶
在由程序直接访问的这部分内存也叫**主存**。当整个树索引都在主存里,沿着指向下一个节点的引用即可访问它。若索引在磁盘上,而节点散落在不同的块里,每多一层就可能多读一块数据。这样的块读写也叫**块 I/O**(输入/输出)。一个块通常能存下多个键和指针,可以用一个块来指向许多子树,压低需要走的层数。
假设根节点有两个键 20 和 50。查找键 37 时,只需在根块内决定走 (20, 50) 那个子树,再去读对应块。块内可以从头比每个键;由于键有序,也可用二分查找每次排除一半位置。这里比较的主要成本是读了几个块。
维护平衡要付出什么¶
让每个节点用一组排序后的键划分多个方向,并让树末端的叶子处在同一深度,这个设计叫 B 树。插入而节点装满时,典型做法是分裂节点并把一个分隔键向上调整。根分裂时,树长高一层。删除也可能移动键、合并节点或使树变矮。
如果常查「键在 50 到 80 之间的全部记录」,希望找到第一条以后能顺着读。**B+ 树**把记录或记录位置集中在叶子节点,把叶子按键的顺序串起来。上面的节点负责带我们找到第一片叶子,之后可以沿链接读下去。节点加大可以降低层数,也会放大某些写入和更新的成本。选择时要看块大小、读写比例和范围查询是否常见。
自测¶
在缓存足够大、索引完全驻留内存时,B 树的块 I/O 优势会如何变化?
参考思路
磁盘 I/O 减少后,比较会转向 CPU 缓存局部性、块内查找时间、指针开销和更新成本。多键节点仍可能有性能优势,大小需要针对内存访问方式评估。