CODEWITHSUNDEEP
data-structurestreebinary-treebinary-search-treeb-tree
Geek
Geek

Reputation: 27193

Why do we need a separate datastructure like B-Tree for database and file system?

I am reading up on B Trees and looks like they achieve the dynamic set operations in O(lg n) time . The Red Black Tree( TreeMap in java ) also achieves the same operation in asymptotically the same time frame . So I would like to know what makes B trees more useful for database and file systems

Upvotes: 26

Views: 9175

Answers (3)

Ivan Vergiliev
Ivan Vergiliev

Reputation: 3841

The main reason for the existence of B-Trees is to better utilize the behaviour of devices that read and write large chunks of data. Two properties are important to make the B-Tree better than binary trees when data has to be stored on disk:

  • Access to disk is really slow (compared to memory or caches, random access to data on disk is orders of magnitude slower); and
  • Every single read causes a whole sector to be loaded from the drive - assuming a sector size of 4K, this means 1000 integers, or tens of some larger objects you're storing.

Hence, we can use the pros of the second fact, while also minimizing the cons - i.e. number of disk accesses.

So, instead of just storing a single number in every node that tells us if we should continue to the left or to the right, we can create a bigger index that tells us if we should continue to the first 1/100, to the second or to the 99-th (imagine books in a library sorted by their first letter, then by the second, and so on). As long as all this data fits on a single sector, it will be loaded anyway, so we might as well use it completely.

This results in roughly logb N lookups, where N is the number of records. This number, while asymptotically the same as log2 N, is actually a few times smaller with large enough N and b - and since we're talking about storing data to disk for use in databases, etc., the amount of data is usually large enough to justify this.

The rest of the design decision are mainly done in order to make this one work efficiently, as modifying a N-ary tree is trickier than a binary one.

Upvotes: 32

user448810
user448810

Reputation: 17876

We need different algorithms because access speed in memory is very much faster than on disk. A red/black tree makes many memory accesses, so it works well with the fast access speed of memory. A b-tree makes fewer, larger accesses because the disk that is accesses is slow.

Upvotes: 2

Jörg W Mittag
Jörg W Mittag

Reputation: 369458

RB trees are binary search trees. B trees can have more than two child nodes. In fact, the number of child nodes is variable.

So, you can vary the number of child nodes such that the size of a node is always a multiple of the filesystem block size. This reduces waste when reading: you cannot read less than one block anyway, you always have to read the full block, so you might just as well fill it up with useful data. Increasing the number of child nodes will also decrease the depth of the tree, thus decreasing the average number of "hops" (i.e. disk reads), which again increases performance.

Remember: B trees are usually used to store data structures which are orders of magnitude larger than memory, whereas RB trees are typically used to store data structures which are orders of magnitude smaller than memory. In fact, B trees are specifically designed as an on-disk data structure as opposed to an in-memory data structure.

This is the key sentence from the Wikipedia article (emphasis mine):

the B-tree is optimized for systems that read and write large blocks of data

Upvotes: 12

Related Questions