B-tree for storage on disk

Why is B-Tree the preferred storage structure on disk?
Which quality makes it preferable for a binary tree for secondary storage.
Is this particular “quality” a sign of the alogrit itself or how it is implemented?
Any link or pointer would be greatly appreciated.

+6
source share
1 answer

The drive is looking expensive. The B-Tree structure has been specifically designed to avoid as many disk attempts as possible. Therefore, B-Tree combines many more keys / pointers into one node than a binary tree. This property makes the tree very flat. Typically, most B-trees are only 3 or 4 levels deep, and the root of the node can be easily cached. It takes only 2-3 searches to find anything in the tree. Leaves are also “packed” in this way, so repeating a tree (for example, a full scan or a range scan) is very effective because you read hundreds / thousands of rows of data per block (search).

In a binary tree of the same capacity you will have several tens of levels and a sequential visit to each individual value will require at least one search.

+6
source

Source: https://habr.com/ru/post/954399/


All Articles