为什么添加索引后会提升数据库查询效率

1. 没有索引时假设有一张用户表user -------------------------------- id name age 1 Tom 18 2 Jack 20 3 Lucy 22 ... 10000000 ...执行SELECT * FROM user WHERE name Lucy;如果name没有索引数据库只能第一行 - 第二行 - 第三行 ...逐条扫描。这个过程叫全表扫描Full Table Scan时间复杂度O(N)1000万条数据最坏需要比较1000万次同时会产生大量磁盘IO。2. 添加索引后例如CREATE INDEX idx_name ON user(name);MySQL(InnoDB)默认采用BTree结构类似root / \ A-H I-Z / \ Jack Lucy查询SELECT * FROM user WHERE nameLucy;数据库会根节点 ↓ 中间节点 ↓ 叶子节点直接定位到数据。不需要扫描全部数据。时间复杂度O(logN)3. 为什么效率高核心原因减少磁盘IO数据库最耗时的不是CPU而是磁盘IO例如CPU计算纳秒级 内存访问微秒级 磁盘访问毫秒级差距几千倍甚至几万倍。BTree会把大量数据组织成多叉树例如每个节点可存1000个key1000万数据第一层1000 第二层 1000 × 1000 100万 第三层 1000 × 1000 × 1000 10亿也就是说1000万数据 只需要3层树查询root ↓ middle ↓ leaf仅需3次磁盘IO即可定位。4. 为什么MySQL不用红黑树很多面试官会追问。红黑树O(logN)看起来一样。但是1000万数据红黑树高度log₂(10000000) ≈ 24需要24次磁盘IO而BTree3~4次IO即可完成查询。所以数据库选择BTree而不是红黑树5. 为什么不用Hash索引Hash结构Tom - hash1 Lucy - hash2 Jack - hash3等值查询where nameLucy非常快O(1)但是where age 20 where age between 20 and 30 order by age无法利用Hash索引。而BTree支持等值查询范围查询排序分组最左前缀匹配因此MySQL默认选择BTree。6. 为什么BTree比B树更适合数据库B树数据分散在所有节点BTree数据全部放叶子节点并且叶子节点双向链表连接1 - 2 - 3 - 4 - 5所以范围查询where age between 20 and 30只需要找到20 ↓ 顺着叶子链表扫描到30效率极高。面试标准回答索引能够提升查询效率本质原因是利用BTree数据结构将原来的全表扫描从O(N)降低为O(logN)。没有索引时数据库需要逐行扫描数据而建立索引后可以通过BTree快速定位目标记录。同时BTree是一种多路平衡查找树树高很低千万级数据通常只需要3~4层因此查询只需3~4次磁盘IO即可完成大幅减少磁盘访问次数。此外BTree叶子节点通过链表连接天然支持范围查询、排序和最左前缀匹配这也是MySQL InnoDB采用BTree作为默认索引结构的主要原因