MongoDB
A document database: BSON collections, WiredTiger B+ trees, replica sets.
MongoDB stores JSON-like BSON documents in collections and serves them through the WiredTiger storage engine, which keeps collections and indexes as B+ trees with page-level MVCC and snapshot checkpoints. Documents group what a relational schema would spread across joins; indexes remain ordinary B+ trees over document fields.
Documents, not rows
A document embeds nested arrays and sub-objects, so one logical entity reads and writes as one unit. The physical cost is paid at index and update time: field updates may move a document across B+ tree pages.
WiredTiger B+ trees
Collections and indexes are B+ trees over on-disk pages with per-page copy-on-write; readers get snapshot isolation while writers produce new page versions.
Journal + checkpoints
Writes are journaled; every 60 seconds (default) WiredTiger checkpoints a consistent snapshot of the data. Recovery restores the last checkpoint and replays the journal.
Indexes are B+ trees too
Single-field, compound, hashed, and text indexes are all tree structures over document fields; query plans choose between index scans and collection scans exactly like a relational planner.
The logical model: nested documents
A document is the unit of storage and retrieval. Where a relational design normalizes an order into orders and order_items tables, MongoDB stores the line items inside the order document. That removes one class of join but moves multi-entity queries and multi-document consistency to explicit operations ($lookup, multi-document transactions).
Physically each BSON document gets a RecordId; the collection is a B+ tree keyed by RecordId, and every index is another B+ tree keyed by the indexed field(s) with RecordIds as values — the same shape a relational index would have over a heap.
// insert + indexed query
db.orders.insertOne({ _id: 1, customer: "ann", total: 42, items: [{sku: "x", qty: 2}] })
db.orders.createIndex({ customer: 1 })
db.orders.find({ customer: "ann" })
The physical model: WiredTiger pages
WiredTiger manages data in on-disk pages of a B+ tree. Updates do not mutate a page: the modified page gets new versions, and readers pinned to older snapshots (MVCC) keep their view until they end. Checkpoints serialize a consistent tree image to disk; the journal covers everything since.
This is a client-server document database, not a storage engine: the mongod process owns durability, replication (oplog), and query execution. Distinguish it from RocksDB in the next exhibit — that one is a library you embed; this one is a server you deploy.
Reads: the planner is familiar
The query planner compares candidate plans (index scan vs collection scan) and caches winners. An explain() output shows IXSCAN/COLLSCAN stages with keysExamined and docsExamined — the same concepts as a relational plan, named differently.
Diagrams
static storyboard — WebGPU animates when available
A live WebGPU particle field tinted to this exhibit. Plays only with WebGPU and no reduced-motion preference; a static storyboard renders for everyone else.
[caption] WiredTiger serves pages under MVCC snapshots; the server layer applies document-level concurrency.
A find() goes through the planner, which picks an index B+ tree scan or a collection scan, then fetches full documents by RecordId.
| insert key | 6 |
| nodes rewritten | 3 (leaf, new leaf, root) |
| height | 2 (unchanged) |
| separator promoted | 6 (copied up — B+ rule) |
All steps
- Insert 6 — route from root — 6 < 10 ⇒ the left leaf L1 [2, 5, 8] owns the range. Root keys are only routers.
- Insert into leaf — Leaf scan places 6 between 5 and 8. Sorted order inside the leaf keeps range scans sequential.
- Overflow — [2, 5, 6, 8] exceeds the 3-key capacity. The leaf must split.
- Split the leaf — Split at the midpoint: left keeps [2, 5], right takes [6, 8]. The leaf linked-list order is preserved.
- Copy separator up — The right leaf’s first key, 6, is copied into the parent as the new separator — data stays in the leaves; the root now routes [6, 10, 20].
- Result — Height unchanged at 2; only 3 nodes rewritten. Splits near the root are what grow a B+ tree; leaf splits are the common case.
A B+ tree insert that overflows a leaf, with the resulting split. Teaching model: max 3 keys per node, two levels. On overflow the leaf splits and the separator (first key of the right leaf) is copied up — B+ behavior; a plain B-tree would move its median key instead.
Teaching model: max 3 keys per node. WiredTiger page sizes, checkpointing, and concurrency control differ; the split rule shown is the general B+ rule.
[caption] Teaching model: max 3 keys per node. WiredTiger page sizes, checkpointing, and concurrency control differ; the split rule shown is the general B+ rule.
Insert a key into a two-level B+ tree: route from the root, overflow the leaf, split it, and copy the separator up — the same mechanics WiredTiger performs per page.
Root, internal, and leaf levels for a compound (customer, date) index at WiredTiger page sizes.
[caption] Illustrative tree for ~5M keys with ~130 entries per leaf page. Real shapes depend on key sizes and WiredTiger page configuration.
Root, internal, and leaf levels for a compound (customer, date) index at WiredTiger page sizes.