索引概念以及索引底层原理

一、什么是索引

索引（index）是帮助MySQL高效获取数据的有序数据结构。在数据之外，数据库系统会维护满足特定查找算法的数据结构（如B+树），这些数据结构以某种方式引用指向数据，从而实现高效查找。

索引的核心作用

1. 提高数据检索效率，降低数据库IO成本，避免全表扫描。
2. 通过索引列对数据进行排序，降低数据排序的成本，减少CPU消耗。

---

二、索引的底层数据结构对比

MySQL的InnoDB存储引擎默认采用B+树作为索引的底层数据结构，在了解B+树前，先对比几种常见数据结构：

1. 二叉搜索树与红黑树

• 二叉搜索树在最坏情况下会退化为链表，查询效率极低。
• 红黑树虽能通过自平衡避免链表退化，但仍属于二叉树，节点分支数少，树高较高，磁盘IO次数多，效率有限。

2. B树（多路平衡查找树）

B树是一种多叉路衡查找树，每个节点可以存储多个key并拥有多个分支。以5阶B树为例，每个节点最多存储4个key。

• 特点：节点同时存储key和数据，所有节点都可以存储数据。
• 缺点：非叶子节点存储数据，导致每个节点能存储的key数量有限，树高仍较高；不适合范围查询。

3. B+树（B树的优化版）

B+树是在B树基础上优化的多路平衡查找树，更适合实现外存储索引结构，也是InnoDB的默认索引结构。

• 结构特点：
  • 非叶子节点只存储键值和指针，不存储数据；数据仅存放在叶子节点。
  • 叶子节点构成双向有序链表，按顺序排列所有数据。

---

三、B树与B+树的核心区别

对比维度	B树	B+树
数据存储位置	所有节点都可存储数据	仅叶子节点存储数据，非叶子节点仅存键值和指针
树高与磁盘IO	节点存储数据，单节点key数量少，树高较高，磁盘IO次数多	非叶子节点不存数据，单节点可存储更多key，树高更低，磁盘IO次数更少
查询效率	效率不稳定，根节点命中最快，叶子节点命中最慢	效率稳定，任何查询都需从根节点走到叶子节点，IO次数固定
范围查询	不支持高效范围查询，需多次遍历	叶子节点为有序双向链表，范围查询可直接遍历链表，效率极高
全表扫描	需遍历所有节点	直接遍历叶子节点的有序链表即可完成全表扫描

---

面试相关问题

1. 问：什么是MySQL索引？它的作用是什么？ 答：索引是帮助MySQL高效获取数据的有序数据结构，作用是提高数据检索效率，降低IO成本；同时通过索引列排序，降低排序的CPU消耗。

2. 问：MySQL的索引为什么用B+树而不是B树？ 答：B+树相比B树有以下优势：

   1. 非叶子节点不存数据，单节点可存储更多key，树高更低，磁盘IO次数更少。
   2. 查询效率稳定，所有查询都需走到叶子节点，性能波动小。
   3. 叶子节点是有序双向链表，范围查询和全表扫描效率更高。

3. 问：B树和B+树的主要区别是什么？ 答：核心区别有三点：

   1. 数据存储位置：B树所有节点都存数据，B+树仅叶子节点存数据。
   2. 磁盘IO效率：B+树树高更低，IO次数更少。
   3. 范围查询能力：B+树叶子节点有序链表，范围查询效率远高于B树。

4. 问：为什么说B+树的查询效率比B树更稳定？ 答：因为B树的查询效率取决于数据所在节点，根节点命中仅需1次IO，叶子节点命中需遍历树高次IO；而B+树无论查询什么数据，都必须从根节点走到叶子节点，IO次数固定，效率更稳定。

5. 问：为什么B+树更适合做数据库索引？ 答：主要有三个原因：

   1. 磁盘读写代价更低，树高更低，IO次数更少。
   2. 查询效率稳定，性能波动小。
   3. 叶子节点的有序链表结构，更适合数据库中常见的范围查询和排序操作。