B-tree与BST查询的磁盘读取及缓存缺失问题问询

问题1：B-tree查询的磁盘读取与处理器对比逻辑是否准确？ #

给定B-tree结构 #

[10, 20]
         /     |      \
 [1, 5, 7] [15, 18] [25, 28, 30, 35]

查询SELECT * FROM table WHERE id = 15的理解流程 #

• 第一步：从磁盘单次读取根节点[10, 20]到内存，处理器对比后确定访问子节点[15, 18]；
• 第二步：从磁盘读取该子节点到内存，处理器在节点内定位到key=15。

解答 #

你的理解完全准确，没有遗漏或误解。B-tree的查询逻辑就是从根节点开始，每次读取一个磁盘节点（对应磁盘上一个物理块）到内存，在内存中通过二分或顺序查找确定下一个要访问的子节点，直到找到目标key所在节点。你描述的两次磁盘读取、内存内对比的流程完全符合B-tree的查询机制。

问题2：关于BST与B-tree内存访问的疑问 #

引用Stack Overflow语句 #

A BST touches fewer memory locations on lookups than B trees, but the cost of those accesses is high because each access likely costs a cache miss.

给定转换后的BST结构 #

10
       /    \
      5      20
     / \    /  \
    1   7  15   30
               /  \
              25   35
                 \
                 28

查询SELECT * FROM table WHERE id = 15时，BST需访问3个节点（10、20、15），B-tree仅需访问2个节点。针对语句的三个子问题解答：

1. 此处“Fewer Memory Locations”的含义是什么？

这里的内存位置指被访问的独立缓存行或内存页数量。BST的每个节点通常是独立的小内存对象，仅包含key、子节点指针，单个节点大概率只占1个缓存行；而B-tree的每个节点对应磁盘上一个大物理块（比如4KB），加载到内存后是一整个内存页，包含多个key和子节点指针。

2. 为何这些访问的成本因缓存缺失而高昂？

CPU缓存是分层的（L1、L2、L3），如果要访问的数据不在缓存中，会触发缓存缺失，需要从内存甚至磁盘加载数据，耗时是缓存命中的几百到几千倍。
BST的节点分散存储，内存地址不连续，每次访问下一个节点时，数据几乎不在当前缓存范围内，大概率触发缓存缺失；而B-tree节点按块加载，一个节点包含多个key，加载一次就能在内存中处理多组对比，缓存命中率高，缓存缺失次数少。

3. 为何BST的3次节点访问被认为比B-tree的2次节点访问涉及更少内存位置？

BST的3个节点是3个独立小内存对象，总共仅占3个左右的缓存行；而B-tree的2个节点是两个完整内存页（比如每个4KB），每个节点对应上百个缓存行。虽然BST访问次数更多，但“触碰”的独立内存单元（缓存行/页）总数量远少于B-tree，这就是这句话的核心逻辑。

内容的提问来源于stack exchange，提问作者Tom