How much do B-trees reduce disk accesses?

Question

I have just read B-trees data structure and I have some questions. I have a doubt in my mind that is not explained in any of the blogs (maybe it's too obvious and I am missing it).

B-trees are supposed to reduce disk accesses by reducing the height of tree. So, if reducing the number of disk accesses is the main concern then how much difference it makes? Suppose I just use binary trees then my nodes need less space than nodes of n-ary B-trees. So I can accommodate more nodes in a page as I can do with fat B-trees nodes. How does it affect disk accesses exactly? Are we talking about worst case only?

Answer 1

You have to understand that B-trees are usually used in systems where you have paged data access. This is most commonly a database system. A page is essentially a block of memory which you have to read (and write) at once. You cannot read individual parts of the page without reading the whole page.

The important thing is: Reading pages from disk into memory is expensive; way more expensive than doing whatever with a page that is already in memory. As such, you want to minimize the number of pages you have to read.

B-trees have several benefits over binary trees for that purpose—which is little surprising considering that they were especially designed for that purpose.

One of these benefits is a reduced height. If you take normal binary trees, you can quickly search within those. But while doing that, you walk very deep into the tree. A binary tree with 1 million elements already has a depth of 20. So, assuming it is balanced, you need to walk down 20 nodes. Comparing that with a B-tree, the height is a lot lower. With a configured children count of 10 (which would be very low btw.) we already have the height down to approximately 6. So we need to make a lot less comparisons, and likely load a lot less pages. Usually, the order of a B-tree (that is the number of children each node has) is chosen in a way, so a single node fills a complete page. Now that may sound stupid as you would need to search within that node’s keys then, but it heavily reduces the depth and as such the amount of pages you have to read.

Another benefit is that B-trees are balanced. This ensures that all nodes at all time are filled approximately with an equal amount of children. Often, this is about 75% of its capacity. Since nodes fill a complete page, this means that every page holding a node is filled to that amount of its capacity. That is very good since that optimizes the space used by nodes and avoids holes in pages that don’t contain information (this would be a big issue with binary trees since they are not balanced by design). Another very important impact is that this also ensures that the number of operations (and as such the run time) to find elements is consistent. So you have a very predictable performance for all cases. For databases, this is usually a lot more important than having better best or average cases which may vary in performance.

There are other benefits too, like having leaves not only all at the same level but also being physically located close to each other, as this improves seek time when iterating through elements.

Basically, B-trees are optimized for paged data access which makes them very special and fine-tuned for those purposes, allowing them to outperform classic binary trees (which are simpler and more efficient in many other applications).

Answer 2

The B stands for balanced, which denotes that in a B-tree the left and right side of each node is roughly kept to the same size (number of subnodes).

Consider this example: Adding numbers to a binary tree as follows: If the new number is larger than the current node add it to the right otherwise to the left (sub-)tree in the same manner.

A) Think about what happens if you add the numbers from 1 to 100 in ascending order.

B) Now imagine what happens if you add them like this 50, 25, 75, 12, 37, 62, 87, ... (That is starting in the middle of the interval and then recursively adding the midpoints of the new intervals)

B-trees add new nodes in such a way that even if you add them ordered like in A) the resulting tree resembles the tree resulting from B)

AS for disk accesses, just imagine having to look up node 100 in the trees from A) and B) and compare how many nodes (disk accesses) you have to process to reach it.

EDIT As it has been pointed out in the comments the above presentation of B-trees is not quite correct.

A B-tree is more like a tree of sorted (node-)lists, that is, each node consists of a sorted list of keys (which is of variable but limited length), each of which references a child node or leaf (data node). This allows the tree to be even flatter than a balanced binary tree (which is basically what I described above). Each node can be considered a chunk or page of data that has to be read in its entirety. Due to the tree being relatively flat, the number of pages that has to be read to lookup a specific data point is low. The complexity of a lookup in a B-tree is comparable to that of a balanced binary tree (or a simple binary search on a sorted list for that matter). The difference lies within the number of keys/data that has to be processed in one step. A binary trees requires one read operation of a single datapoint per level, a sorted list requires all data to be read at once, and a B-tree lies in the middle by requiring a chunk of data per level. From a number of operations point of view that is irrelevant, from a memory access point of view it is very important. When reading data from a disk, the size of the chunks is less important (as long as it is limited) than the number of separate read operations required.