B-Trees, LSM Trees, and the Indexing Tradeoff Spectrum

This article is part 4 of a 10-part series on query engine design, focusing on auxiliary data structures that speed up data lookups: indexes. It covers the fundamental tradeoff that every index speeds up reads but slows down writes. The article details B-Trees as the OLTP standard used in databases like PostgreSQL and MySQL, explaining point lookups, range scans, and write costs. It then covers LSM Trees designed for high write throughput, with memtables and SSTables. Additionally, it mentions bitmap indexes for OLAP filtering, zone maps, and inverted indexes for full-text search. The content includes a tradeoff matrix and real-world system examples, making it highly relevant to IT/technology professionals interested in database internals and indexing strategies.