B-tree is a self-balancing data structure that maintains sorted data. This allows lookups (reads) to be very fast, since the tree can be shallow but wide.
B-trees offer
- Great read latency, since everything is sorted and the tree is shallow
- Not so great write latency, since inserts must go into the right place to maintain ordering. This may also trigger a node split to maintain balance, which increases latency. This makes the write latency non-deterministic.
Its implementation also requires special care for crash consistency and concurrency.
B-epsilon tree
B-epsilon trees improve the write performance of B-trees by allowing writes to be cached at the nodes. As writes come in, they go into buffers until the buffers fill, and only then are the inserts actually applied to the tree.
This write optimization makes reads more complicated, since read-after-write requires dealing with buffered inserts.