While other answers correctly mention that WiredTiger defaults to a B+ Tree, it’s important to clarify that WiredTiger specifically uses these structures for storing table data in memory. The explanation provided by Keith Smith sheds further light on this topic:
Within the WiredTiger team, we tend to refer to our tables "B-Trees". I think this is mostly for simplicity, and not because it is the precisely correct term. But that does lead to some inconsistency (as you've found) in the documentation and comments.
The exact answer, however, is a bit complicated. WiredTiger includes a number of optimizations and design choices that don't adhere to the classic definitions of a B-Tree or a B+ Tree. I expect that if you look in detail at any other widely used database you will find similar variations.
There is not, to my knowledge, a precise definition of a B+ tree. Two features that are commonly cited are:
All keys reside in the leaves.
The leaves are linked for easy sequential access.
WiredTiger B-Trees do store all keys and values in the leaf pages. (An exception are overflow pages where we store large keys and values that might be inefficient to store in the leaf page. This is one of those optimizations I mentioned.) So in that regard they behave like B+ trees.
WiredTiger does *not* (as you've found) provide links directly from one leaf page to the next. This is because WiredTiger always writes an updated page to a new location in the file. So linking leaf pages in this manner would be impractical. When we update a leaf page, we write it to a new file location. That means we would need to update the pointer in the leaf pages pointing to it, and therefore we would write those pages to new locations, until we rewrite every leaf page.
WiredTiger moves from one leaf page to the next by going back through the parent page. This is pretty efficient because the WiredTiger cache will never evict an internal B-Tree page if any of its child pages are in the cache. Therefore any time we need to move from one leaf to the next, the parent is guaranteed to be in the cache.
FWIW, Douglas Comer's classic paper on B-Trees from 1979 says that in B+ trees "leaf nodes are *usually* linked together" (p. 129, emphasis mine). So it has never been a strict requirement that B+ trees have these links.
Keith
Reference: https://groups.google.com/g/wiredtiger-users/c/1YHbNXPw-1A
WiredTiger follows a B+ Tree-like structure but with notable deviations. It stores all keys and values in leaf nodes but does not link them directly. Instead, it navigates between leaf nodes through the parent node, leveraging caching to maintain efficiency. This design choice avoids excessive rewrites caused by WiredTiger’s approach of writing updated pages to new file locations.