在维基百科 B 树的“搜索已排序文件的时间”部分,它说
With 100 records per block, the last 6 or so comparisons don't need to do any disk reads—the comparisons are all within the last disk block read.
https://en.wikipedia.org/wiki/B-tree#Time_to_search_a_sorted_file
问题:20次比较中,为什么最后6次比较不需要读盘?
最佳答案
最后 6 次比较都是针对读入内存的最后 100 条记录 block 进行的:2^6 = 64,并且 64 < 100。
B-tree:每次查找都会将之前的查找空间减半(参见“分而治之”)。到域缩小到该级别时,所有数据“在物理上非常接近”。在此示例中,这是在已读入内存的连续 100 条记录的单个 block 内,从而避免了额外的 IO 读取。
之前的 (14) 次比较很可能必须读取不同的 记录/记录 block ,这会导致 IO 读取,不包括缓存。
关于algorithm - B-tree disk read requirement 解释想要,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47965612/