MongoDB WiredTiger Simplifies Concurrency Control by Removing Page Links

Unlike traditional B+Trees, the WiredTiger storage engine in MongoDB v6.0 does not maintain links between pages at the same level. This removes the need to modify pointers of adjacent pages and complex locking procedures during Page Splits, simplifying atomic operations and reducing the complexity of concurrency control.

Inside leaf pages, two data structures are mixed to balance read and write performance. Sorted records loaded from disk (WT_ROW) are stored in arrays to support fast lookups via binary search. Conversely, skip lists are used for inserting new keys to avoid the cost of shifting elements in arrays. Modifications or deletions of existing keys are managed as linked lists through WT_UPDATE structures, which support MVCC (Multi-Version Concurrency Control).

In comparison with InnoDB, WiredTiger adopts Optimistic Concurrency Control instead of maintaining page links, while InnoDB maintains bidirectional linked lists between pages and uses Pessimistic Concurrency Control. Test results showed that lookups via in-memory skip lists resulted in a performance difference of about 7% depending on the sort direction, whereas there was almost no difference in lookups via WT_ROW arrays.