Why does MongoDB use B-Tree instead of B+Tree for indexing?

MongoDB Atlas Atlas Search
1

I have been researching how indexes work in different database systems, and I found that most relational databases like MySQL (InnoDB), PostgreSQL, and Oracle use B+Tree for indexing.
However, in the MongoDB documentation, it is mentioned that indexes in MongoDB use B-Tree rather than B+Tree.

:small_blue_diamond: My understanding is that B+Tree is generally more efficient for range queries (BETWEEN, ORDER BY) because:

  • Data is stored only in leaf nodes, while internal nodes are used for navigation.
  • Leaf nodes are linked, making sequential scans faster.
  • B+Tree maintains a consistent structure for inserts/updates, reducing fragmentation.

:small_blue_diamond: Meanwhile, B-Tree stores data in both internal nodes and leaf nodes, which might lead to:

  • Less efficient range queries.
  • More complex insert/update operations.
  • Possibly worse performance for full table scans.

Given these differences, my question is:

Why does MongoDB use B-Tree instead of B+Tree for indexing?

  • Is there a specific reason related to MongoDB’s architecture that makes B-Tree a better fit?
  • Does MongoDB implement any optimizations to improve the efficiency of range queries despite using B-Tree?
  • Could there be any plans to adopt B+Tree in future versions for better performance?

Any insights from MongoDB engineers or database experts would be greatly appreciated. Thanks in advance!

3

Perhaps this answer from Keith Smith of WiredTiger team can help - WT actually uses something that’s got some features of B±trees.

4

Question: Why does MongoDB use B-Tree instead of B+Tree for indexing?

Answer: MongoDB uses B-Tree because it allows faster access to both keys and values at all levels, not just at the leaf level like in B+Tree. This suits MongoDB’s document-based access patterns.