B+Tree vs LSM Tree: Why Your Database's Data Structure Is Everything

In Post 1, we looked at a benchmark result where Cassandra wrote 2× faster than PostgreSQL — then read 3× slower before compaction ran. Same hardware. Same data. Wildly different numbers in both directions. That result is a direct consequence of the data structures each engine is built on. Cassandra and PostgreSQL made opposite choices at the foundation level, and those choices ripple through every read, every write, and every latency number you'll ever measure. This post explains those choices. The Problem All Database Indexes Must Solve Before we look at any specific data structure, let's talk about why this problem is hard. You want three things from a database index: Fast writes. When you insert an order, the index should update quickly. Fast reads. When you query by order_id, finding the right row should take as few disk operations as possible. Efficient range scans. When you query orders between two dates, the engine should be able to find the start of the range and read forward