Q24: How do B-Tree and Hash Indexes work internally?
- B-Tree Index: A self-balancing search tree structure that keeps indexed data sorted. It efficiently processes exact equality matches (
=), range scans (>,<,BETWEEN), andORDER BYoperations in logarithmic time ($O(\log N)$). - Hash Index: Uses hash tables to map key values to row locations. It provides constant-time $O(1)$ lookups for equality checks (
=), but cannot support range queries or ordering operations.
Key Takeaways
- B-Trees are the default index type because they support both range lookups and equality matches efficiently.
- Hash indexes offer fast equality lookups, but do not support range scans or sorting.