How does MongoDB BTree Index perform Node rebalancing?

[Weishan Ang]

I'm trying to understand the internals of MongoDB BTree index, especially on the behaviour of node rebalancing and concurrency of the BTree during insertion and updates.

I did some digging on PostgreSQL and discover that it is based on Lehman and Yao's paper with some modification on it. Instead of locking the entire tree and rebalance the BTree, it holds a write-lock on the node it is splitting and the former right sibling so that it can update the left link of the former right sibling. 

I wonder if there's anyone here who can share more details or point me in the right direction on MongoDB BTree algorithm.

Regards,

Wei Shan

[Geert Bosch]

On Aug 20, 2017, at 8:34 PM, Weishan Ang <weish...@gmail.com> wrote:

I'm trying to understand the internals of MongoDB BTree index, especially on the behaviour of node rebalancing and concurrency of the BTree during insertion and updates.

This depends on the specific storage engine. MongoDB itself just requires that a storage engine implements our SortedDataInterface class, which may or may not be done using BTrees. For example, the RocksDB storage engine will always use LSM trees. For our WiredTiger and MMAPv1 storage engines, we use BTree implementations. Although WiredTiger also supports LSM and columnar storage formats, we don't use these currently.

I did some digging on PostgreSQL and discover that it is based on Lehman and Yao's paper with some modification on it. Instead of locking the entire tree and rebalance the BTree, it holds a write-lock on the node it is splitting and the former right sibling so that it can update the left link of the former right sibling. 

For MMAPv1, writes lock the entire collection, so concurrency is limited.

For WiredTiger, see https://www.mongodb.com/presentations/webinar-a-technical-introduction-to-wiredtiger for more information.

  -Geert

I wonder if there's anyone here who can share more details or point me in the right direction on MongoDB BTree algorithm.

Regards,

Wei Shan

--
You received this message because you are subscribed to the Google Groups "mongodb-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mongodb-dev...@googlegroups.com.
To post to this group, send email to mongo...@googlegroups.com.
Visit this group at https://groups.google.com/group/mongodb-dev.
To view this discussion on the web visit https://groups.google.com/d/msgid/mongodb-dev/37a4f592-2803-4f2e-afd9-d012af2d8bd0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Weishan Ang]

Hi Greet,

Thanks for the response.

I will post the question to the WiredTiger mailing list instead then.