http://databasearchitects.blogspot.com/2024/06/b-trees-require-fewer-comparisons-than.html

Database Architects

A blog by and for database architects.

Thursday, June 6, 2024

B-trees Require Fewer Comparisons Than Balanced Binary Search Trees

Due to better access locality, B-trees are faster than binary search
trees in practice -- but are they also better in theory? To answer
this question, let's look at the number of comparisons required for a
search operation. Assuming we store n elements in a binary search
tree, the lower bound for the number of comparisons is log[2] n in
the worst case. However, this is only achievable for a perfectly
balanced tree. Maintaining such a tree's perfect balance during
insert/delete operations requires O(n) time in the worst case.

Balanced binary search trees, therefore, leave some slack in terms of
how balanced they are and have slightly worse bounds. For example, it
is well known that an AVL tree guarantees at most 1.44 log[2] n
comparisons, and a Red-Black tree guarantees 2 log[2] n comparisons.
In other words, AVL trees require at most 1.44 times the minimum
number of comparisons, and Red-Black trees require up to twice the
minimum.

How many comparisons does a B-tree need? In B-trees with degree k,
each node (except the root) has between k and 2k children. For k=2, a
B-tree is essentially the same data structure as a Red-Black tree and
therefore provides the same guarantee of 2 log[2] n comparisons. So
how about larger, more realistic values of k?

To analyze the general case, we start with a B-tree that has the
highest possible height for n elements. The height is maximal when
each node has only k children (for simplicity, this analysis ignores
the special case of underfull root nodes). This implies that the
worst-case height of a B-tree is log[k] n. During a lookup, one has
to perform a binary search that takes log[2] k comparisons in each of
the log[k] n nodes. So in total, we have log[2] k * log[k] n = log[2]
n comparisons.

This actually matches the best case, and to construct the worst case,
we have to modify the tree somewhat. On one (and only one) arbitrary
path from the root to a single leaf node, we increase the number of
children from k to 2k. In this situation, the tree height is still
less than or equal to log[k] n, but we now have one worst-case path
where we need log[2] 2k (instead of log[2] k) comparisons. On this
worst-case path, we have log[2] 2k * log[k] n = (log[2] 2k) / (log[2]
k) * log[2] n comparisons.

Using this formula, we get the following bounds:
k=2: 2 log[2] n
k=4: 1.5 log[2] n
k=8: 1.33 log[2] n
k=16: 1.25 log[2] n
...
k=512: 1.11 log[2] n

We see that as k grows, B-trees get closer to the lower bound. For k>
=8, B-trees are guaranteed to perform fewer comparisons than AVL
trees in the worst case. As k increases, B-trees become more
balanced. One intuition for this result is that for larger k values,
B-trees become increasingly similar to sorted arrays which achieve
the log[2] n lower bound. Practical B-trees often use fairly large
values of k (e.g., 100) and therefore offer tight bounds -- in
addition to being more cache-friendly than binary search trees.

(Caveat: For simplicity, the analysis assumes that log[2] n and log
[2] 2k are integers, and that the root has either k or 2k entries.
Nevertheless, the observation that larger k values lead to tighter
bounds should hold in general.)


Posted by Viktor Leis at 3:59 PM #
Email ThisBlogThis!Share to TwitterShare to FacebookShare to
Pinterest

No comments:

Post a Comment

 

Older Post Home
Subscribe to: Post Comments (Atom)

Contributors

  * Peter Boncz
  * Thomas Neumann
  * Viktor Leis

Blog Archive

  * V  2024 (2)
      + V  June (1)
          o B-trees Require Fewer Comparisons Than Balanced Bi...
      + >  February (1)

  * >  2023 (3)
      + >  April (1)
      + >  February (1)
      + >  January (1)

  * >  2022 (7)
      + >  June (5)
      + >  April (1)
      + >  January (1)

  * >  2021 (2)
      + >  July (1)
      + >  June (1)

  * >  2020 (4)
      + >  November (1)
      + >  October (1)
      + >  April (1)
      + >  January (1)

  * >  2019 (3)
      + >  July (1)
      + >  May (1)
      + >  February (1)                                           

  * >  2018 (2)
      + >  June (1)
      + >  April (1)

  * >  2017 (2)
      + >  December (1)
      + >  February (1)

  * >  2016 (2)
      + >  August (1)
      + >  April (1)

  * >  2015 (7)
      + >  December (1)
      + >  September (1)
      + >  July (1)
      + >  June (1)
      + >  April (1)
      + >  February (1)
      + >  January (1)

  * >  2014 (11)
      + >  December (1)
      + >  September (1)
      + >  August (1)
      + >  July (2)
      + >  June (2)
      + >  May (4)

 
Simple theme. Powered by Blogger.