B+ Tree

Data

B+ Tree

A balanced tree with all data in the leaves and high fan-out, so a billion rows is only four levels deep.

Why interviewers ask about it

Explains why indexed lookups are fast regardless of table size, and why in-place updates make writes random I/O - the contrast with LSM.

LSM Tree

Writes buffer in a memtable and flush as immutable sorted files, merged by background compaction.

This term is part of the free System Design interview preparation module - browse the full glossary for every definition.