InnoDB-indexes zijn B+trees: gebalanceerde bomen waar elke leaf op dezelfde diepte zit en de leaves gekoppeld zijn voor snelle range scans. Een lookup is O(log n) — een handvol page reads, zelfs op enorme tabellen.
Composite indexes en de leftmost prefix
Een composite index sorteert rijen op , dan , dan . Je kunt hem alleen gebruiken voor een van de kolommen: , of — maar alleen of , omdat die kolommen niet gesorteerd zijn tot vaststaat.
