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

Question

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

Answer 1

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 log_b N lookups, where N is the number of records. This number, while asymptotically the same as log₂ 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.