CODEWITHSUNDEEP
data-structuresb-tree
user7826451
user7826451

Reputation:

What makes B-tree well suited for discs

What exactly makes B-tree well suited for discs? I thought that it is because discs can read sequential data really fast but it takes significantly more time for disc to seek another location, but I can't really find any explanation for people with little knowledge about discs and their operations.

Upvotes: 0

Views: 25

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

If you put 1 million things in a binary search tree, then you have to follow about 20 pointers to find one when you do a search.

If the data structure is on disk, then following a pointer means doing a seek, and 20 seeks is pretty slow.

If you put the same 1 million things in a B-tree or B+tree, then you only have to follow 2 or 3 pointers to find one of them when you do a search, using realistic node sizes.

That's up to 10 times faster.

Upvotes: 1

Related Questions