CODEWITHSUNDEEP
mongodbgeospatialb-treespatial-index
dykw
dykw

Reputation: 1249

Why not B+-Tree MongoDB

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.

Upvotes: 10

Views: 4268

Answers (4)

Apurva Singh
Apurva Singh

Reputation: 5010

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.

Upvotes: 0

陈Jifan
陈Jifan

Reputation: 31

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

Upvotes: 3

Ethan
Ethan

Reputation: 704

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.

Upvotes: 3

user4829806
user4829806

Reputation:

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.

Upvotes: 0

Related Questions