Databases & System Design•Part 2: Relational Databases (RDBMS / PostgreSQL / MySQL) (6 - 25)
How do B-Tree indexes work internally?
In Simple Words:
B-Trees are self-balancing search trees with shallow depth and high branching fanout. Keys are kept sorted, allowing $O(\log N)$ search, insert, and delete operations. In B+Trees, all data pointers live in linked leaf nodes, making range queries (BETWEEN, >, <) exceptionally fast.
sql
-- Default index type in PostgreSQL is B-Tree:
CREATE INDEX idx_products_price ON products USING btree (price);
-- B-Tree efficiently handles equality and range queries:
SELECT * FROM products WHERE price BETWEEN 20.00 AND 50.00;