Searching a B-Tree Index: What is the base of log in O(log n)?

Question

Searching a database B-Tree index can be performed in O(log n) time.

For a B-Tree index, what is the base of log?

I know that in Big-O notation, the base does not matter. Regardless I'm curious what the base is for B-Tree indexes.

For example, a binary search on a sorted list has a base of 2 in O(log n). This is because we can discard half the list on each comparison.

Likewise, a binary search on a balanced binary tree is base 2 for the same reason.

Answer 1

The base of the log function really doesn't matter.

By changing the base, you change only a constant multiplication factor to apply to the speed of the processor on which the code runs.

That said, B-Tree indexes in DBs have branching factors (the number of children per node) that depend inversely with the quantity of bytes needed to store the value being indexed, specifically varying with ^{(I/O page size)}/_{(entry byte size)}.

For postgres, the branching factor can number in the low thousands for small sized entries. For MySql, it might be about 50. In general, database btree have high branching factors to minimize disk page reads, which are in the order of 1000 times slower than the time it takes to process the page.

The number of nodes traversed varies with O(log_bn) where b is the branching factor and thus the base of the log.