CODEWITHSUNDEEP
algorithmb-tree
suztomo
suztomo

Reputation: 5202

B-tree disk read requirement explanation wanted

In Wikipedia B-tree's "Time to search a sorted file" section, it says

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

Question: among the 20 comparisons, why do not the last 6 or so comparison need any disk read?

Upvotes: 1

Views: 68

Answers (1)

user2864740
user2864740

Reputation: 61865

The last 6 comparisons are all done against the last 100-record block read into memory: 2^6 = 64, and 64 < 100.

B-tree: each lookup reduces the previous lookup space by half (see "divide and conquer"). By the time the domain has been reduced to that level all the data is 'physically very close together'. In this example, that is within a single block of contiguous 100 records that have already been read into memory, thus avoiding additional IO reads.

The previous (14) comparisons would most likely have to read different records/record blocks which - excluding caching - would have resulted in IO reads.

Upvotes: 2

Related Questions