How to estimate the average base of the logarithm for a MongoDB index lookup?

Working with Data
, ,
1

I’m trying to understand how the O(log N) complexity of a MongoDB index lookup translates to actual performance. MongoDB uses B-trees (B+trees) for indexes, and the logarithm’s base corresponds to the fanout (number of keys per node).

  1. I want to estimate the average base of the logarithm for a given index. Specifically:

  2. How can I determine or approximate the typical number of keys per index node in MongoDB?

  3. Given the number of entries in an index (e.g., 10 million), how can I use this to estimate the height of the B-tree or the number of node accesses needed for a lookup?

Are there practical rules of thumb or formulas to approximate the “effective base” of the log for different types of fields (integers, short strings, compound indexes)?

I’m looking for a way to reason about log(N) in MongoDB indexes more realistically, rather than just assuming a binary tree with base 2.

Thanks for any insights!