CODEWITHSUNDEEP
algorithmdata-structures
IUnknown
IUnknown

Reputation: 9839

B-Tree for on-disk storage

Why is a B-Tree the preferred structure for on-disk storage.
What quality makes it preferrable over a binary tree for secondary storage.
Is that specific 'quality' a feature of the alogrithm itself;or the way in which it is implemented?
Any reference or pointer would be much appreciated.

Upvotes: 8

Views: 5225

Answers (1)

Piotr Kołaczkowski
Piotr Kołaczkowski

Reputation: 2629

Disk seeks are expensive. B-Tree structure is designed specifically to avoid disk seeks as much as possible. Therefore B-Tree packs much more keys/pointers into a single node than a binary tree. This property makes the tree very flat. Usually most B-Trees are only 3 or 4 levels deep and the root node can be easily cached. This requires only 2-3 seeks to find anything in the tree. Leaves are also "packed" this way, so iterating a tree (e.g. full scan or range scan) is very efficient, because you read hundreds/thousands data-rows per single block (seek).

In binary tree of the same capacity, you'd have several tens of levels and sequential visiting every single value would require at least one seek.

Upvotes: 10

Related Questions