Why does an index's internal data structure matter if it all ends up 'faster than a scan'?
Different structures are fast at different operations. A hash table is fast at exact lookups but can't do range scans at all. A B-tree does both reasonably well. A bitmap index is extremely compact for low-cardinality columns but terrible for high-cardinality ones. Choosing the wrong internal structure for your access pattern means the index technically exists but doesn't actually make your queries fast.
Answered in
What Actually Happens Inside a Database Index: The Data StructuresAn index trades disk I/O for lookup speed. Here's how B-trees, hash tables, and bitmap indexes each make that trade differently.
Read the full analysisOther questions this article answers
More system design & architecture questions
- What does CodeDeploy RESTART actually deploy?
- Does CodeDeploy RESTART work with ECS or Lambda?
- Does RESTART remove an application from load-balancer traffic while it restarts?
- Does Elastic Beanstalk's Active Directory join require a domain password?
- Can an Elastic Beanstalk environment be healthy if the domain join fails?
- Will enabling Active Directory replace running instances?
- What is different about AWS Lambda Web Functions?
- Does Lambda Web Functions automatically cost less than ordinary Lambda?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design & Architecture beat.