Why not B+-Tree MongoDB

Question

Do anyone know why MongoDB use B-Tree but not B+-Tree?

As I know most DBMS use B+-Tree. Are there any special reason for MongoDB to use B-Tree?

thanks.

Barrows

While this is an interesting question, I don't think there's any way for someone to give a definitive answer without asking the MongoDB people themselves. – Interpellant

I sent an e-mail to 10gen. They asked me to post my question in their MongoDB forum. But I don't think a lot of people read the forum. I haven't got any reply. – Barrows

You asked it 4 hours ago (as of when I commented). Be a bit more patient. Also -- they may not want to spend the time answering your question. – Ian

Per this doc, WiredTiger maintains a table's data in memory using a data structure called a B-Tree ( B+ Tree to be specific) – Cioban

Answer 1

The question has confused me when I learned B/B+.Now I get some answers:

1. mysql is a relational db, while mongo isn't. It means that we do more range operations in mysql(such as select * from xx where id > 23). So the advantages of B+ tree aren't obvious.
2. B tree's best search time is O(1), while B+ is always O(log n). So when search some 'hot' data. B tree has a better performance.(however if you always search the data in the leaf when using B tree, it takes more disk IO times so it may not perform well.)

In my opinion, it depends on the details how mongo implements.But I am not a Mongo developer. :D

Mernamero

You can do range queries in MongoDB as well. – Harney

Well, actually it does. But B+ tree takes less search, for its extra pointers. – Postiche

Answer 2

MongoDB uses B+ by WiredTiger default storage engine.

1、https://docs.mongodb.com/manual/core/wiredtiger/

Starting in MongoDB 3.2, the WiredTiger storage engine is the default storage engine.

2、http://source.wiredtiger.com/3.2.1/tune_page_size_and_comp.html

WiredTiger maintains a table's data in memory using a data structure called a B-Tree ( B+ Tree to be specific), referring to the nodes of a B-Tree as pages. Internal pages carry only keys. The leaf pages store both keys and values.

Crumple

Answer 3

From what I can figure out, MongoDB stores indexes as part of the same files in which data is stored. So B Tree is better! B+ tree stores data only in the leaves.

Justin

Answer 4

MongoDB v1 use linux mmap i.e. memory mapped file. This uses operating system memory mapping feature to read/write from file. So as data is read, if it is not in memory, it is fetched by the operating system automatically from data file.
The data structure used for files is B Tree. This is preferred because it consumes less space as compared to B+ tree and so better memory utilization. Also, it doesn't necessarily have to go to leaves to get data; data may be found at the top or middle of tree.
In fact, Uber was using MongoDB till 2015 because they could load all their data in RAM, so v1 using B Tree was fast and efficient. They moved to Cassandra when they found that they can no longer rely on data being loaded fully in RAM.
In wired tiger, both B Tree and log structured merge tree are available. You should prefer log structured merge tree.
I guess B Tree still exists in Wired Tiger due to legacy reasons. But log structured merge tree is preferred now. It uses a balanced binary tree like red black tree.

Whew