Indexing: B+ trees
Database Management Systems · Engineering
Study notes
A B+ tree with fan-out 200 and 3 levels holds 200^3 = 8 million keys. Finding a row reads 3 index pages plus 1 data page: 4 disk reads instead of scanning 8 million rows. Range query 'age 20-30' walks the linked leaves sequentially after the first lookup.