# 一、索引
30 秒速记
- 索引就是书的目录：用额外的空间和写入成本，换查询时不用一页页翻（全表扫描）
- 索引在存储引擎层实现，
InnoDB默认用B+ Tree：矮、胖、叶子有序相连，等值、范围、排序都能用 InnoDB主键是聚簇索引，叶子存整行；二级索引叶子存主键值，查别的列要回表- 联合索引看最左前缀；查询的列都在索引里就是覆盖索引，不用回表
- 常见失效：索引列上套函数、隐式类型转换、
LIKE '%xx'前置通配符；索引也不是越多越好，每个都拖慢写入
索引可以理解成书的目录，它用额外的存储空间和写入时的维护成本，换来查询时不用一行行扫全表。 MySQL 里索引是存储引擎实现的，InnoDB 默认用 B+ Tree，树很矮，三四层就能装下千万级数据，叶子节点还按顺序串起来，所以范围查询和排序也能用上。InnoDB 的主键索引叶子里直接存整行数据，叫聚簇索引；二级索引叶子里存的是主键值，查到之后还得拿主键再去主键索引里取一次，叫回表。我做索引设计时主要看三件事：查询条件和联合索引的列顺序对不对得上，能不能做成覆盖索引省掉回表，以及这张表写得多不多，别为了读把写拖垮。
# B+ Tree 原理
面试官追问
追问 1订单表 phone 是 VARCHAR 而且建了索引，WHERE phone = 13800138000 却全表扫描，为什么？
字符串列拿数字去比，MySQL 会把每一行的 phone 转成数字再比较，相当于在索引列上套了函数，索引就用不上了。写成 WHERE phone = '13800138000'。
追问 2WHERE DATE(created_at) = '2026-10-01' 很慢，created_at 明明有索引，怎么改？
对索引列套函数后，B+ Tree 里存的是原值，没法按 DATE() 的结果定位。改成范围：created_at >= '2026-10-01' AND created_at < '2026-10-02'。
追问 3一张只有几百行的配置表，加了索引 EXPLAIN 还是 ALL，索引白建了？
数据太少时，优化器算出来全表扫描比走索引再回表还便宜，就直接扫了，这很正常。小表本来也不用太纠结索引。
追问 4有人给一张写入很频繁的日志表的每一列都加了索引，有什么问题？
每次 INSERT 都要同时维护所有索引的 B+ Tree，写入变慢、占用空间翻倍，而且大部分索引根本用不上。只给真实查询条件建索引，上线前用 EXPLAIN 确认。
追问 5怎么确认一条 SQL 到底有没有用上索引？
EXPLAIN 看 type（const、ref、range 好，ALL 是全表扫描）、key（实际用的索引）、rows（预估扫描行数），Extra 里出现 Using index 说明是覆盖索引。MySQL 8.0.18 以后还能用 EXPLAIN ANALYZE 看真实耗时。
# 1. 数据结构
30 秒速记
B Tree= 平衡多路查找树，所有叶子在同一层，任何一条数据查找路径一样长B+ Tree两点改进：数据只放叶子，内部节点只存键当路标；叶子之间用指针串成有序链表- 内部节点不存数据 → 一页能塞更多键，扇出大、树更矮，磁盘
I/O更少 - 范围查询 = 先从根走到起点叶子（
O(log N)），再顺着链表往后读，不用回到根 InnoDB一页16KB，三层B+ Tree大约能存两千万行，这是估算值不是定数
B Tree 是所有叶子都在同一层的多路平衡查找树，B+ Tree 在它基础上做了两件事：数据只放在叶子，叶子之间用指针串起来。 第一点让内部节点只存键和子指针，一个 16KB 的页能放上千个分支，树就特别矮；第二点让范围查询不用来回爬树，找到起点后顺着叶子链表往后读就行。比如查 price BETWEEN 20 AND 50，先从根往下找到第一个 >= 20 的叶子，再沿链表一直读到超过 50 为止。所以范围查询的代价是「定位起点 + 读结果条数」，结果越多越慢，不是什么 O(1)。
B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。
B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。
在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。
原理拆解： B+ Tree 通过高扇出节点把有序键空间逐层切分。查找一个键时，先在根节点比较分隔键并选择子指针，再在下一层重复，直到到达叶子节点；树始终保持平衡，所以任意叶子的访问层数基本一致。典型实现中，内部节点主要保存分隔键和子指针，完整记录或记录定位信息集中在叶子节点，这使单个内部节点能容纳更多分支，从而降低树高。
查询链路： 查找区间 [20, 50] 时，先按单点查找方式定位第一个不小于 20 的叶子位置，然后沿叶子之间的顺序指针持续扫描，读到大于 50 的键后停止。其代价可理解为定位起点的 O(log_f N) 加返回结果的线性读取量 O(k)，其中 f 是节点扇出、k 是命中记录数；顺序指针减少的是重复从根定位后续键的成本，并不会令范围查询变成 O(1)。
边界与反例： 内部节点分隔区间采用左闭右开、右侧最小键或其他约定，取决于具体实现，不能仅凭相邻键就断言两端都包含。大量相同键还需要配合记录标识或溢出组织方式维持确定顺序。平衡也不代表没有维护成本：插入导致节点溢出时可能分裂并向父节点传播，删除后则可能发生合并或重新分配。
工程验证： 在数据库中可用 EXPLAIN 对比等值查询、连续范围查询和对索引列施加函数后的查询计划，观察是否选择目标索引、预估扫描行数及是否出现额外排序。验证时还应保证统计信息可用并扩大数据量；小表上优化器选择全表扫描可能只是成本估算结果，不能据此判定 B+ Tree 索引失效。
面试官追问
追问 1B Tree 和 B+ Tree 都是平衡多路树，数据库为什么偏偏选 B+ Tree？
B Tree 内部节点也存数据，一页能放的键就少，树更高；范围查询还要中序遍历在不同层之间来回跳。B+ Tree 内部节点只当路标、叶子有序成链，树更矮，范围扫描就是顺着链表读。
追问 2三层的 B+ Tree 大概能存多少行，怎么估出来的？
按 InnoDB 一页 16KB 算，主键 BIGINT 占 8 字节加指针 6 字节，一个内部节点约 1170 个分支；叶子假设一行 1KB，一页放 16 行。1170 × 1170 × 16 约等于两千万，实际随行宽和填充率变化。
追问 3有人说叶子之间有链表，所以范围查询是 O(1)，对吗？
不对。先要从根走到起点叶子，这一步是 O(log N)，然后读 k 条结果就是 O(k)，查一万条和查十条的耗时差别很大。链表省的是每读一条都从根重新找的成本。
追问 4主键查询和二级索引查询，走的 B+ Tree 一样吗？
不是一棵树。InnoDB 每个索引都是一棵独立的 B+ Tree，主键树叶子存整行，二级索引树叶子存主键值，所以二级索引查到主键后还要去主键树再走一遍。
追问 5B+ Tree 的叶子节点之间是单向链表还是双向链表？
InnoDB 里同一层的页之间是双向链表，所以 ORDER BY id DESC 也能直接从右往左扫，不需要额外排序。
# 2. 操作
30 秒速记
- 查找：从根开始，每个节点内二分找到下一层的指针，一路走到叶子，再在叶子里二分定位
- 每层一般就是一次页读取，树高 3~4 层 → 冷数据最多读 3~4 页，根和上层通常常驻缓存
- 插入：先找到目标叶子，页满了就分裂成两页，把分隔键推给父节点，极端时根分裂、树长高一层
- 删除：页太空时和兄弟合并或向兄弟借键；
InnoDB有合并阈值，不是每删一行就立刻重组 - 自增主键总在最右边追加，几乎不分裂；
UUID这种随机主键会到处插，页分裂多、碎片多
B+ Tree 的查找就是从根节点开始，每层在节点里二分找到该往哪个子节点走，一直走到叶子。 树高通常就三四层，而且上层节点基本都在内存里，所以一次主键查询实际的磁盘读取很少。插入和删除的麻烦在于要维持平衡：叶子页满了要分裂成两页，再把分隔键往父节点插，父节点也满了就继续往上分裂；删除让页太空时，会跟兄弟页合并或者借几个键过来。这也是为什么我建表时更喜欢自增主键，新数据永远追加在最右边的页，几乎不分裂，换成随机的 UUID 主键，插入会落到树的各个位置，频繁页分裂，写入变慢，空间也更碎。
进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。
插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性。
原理拆解： B+ Tree 的内部节点只承担导航职责：节点中的分隔键把键空间划成多个区间，节点内二分确定下一页，再沿子指针下降。真正的索引记录集中在叶子层，叶子通常还通过双向链表相连，因此等值查询在叶子命中后结束，范围查询则可继续顺序扫描相邻叶子。树高为 h 时，冷缓存下通常要访问约 h 个索引页；缓存命中会减少物理 I/O，但不会改变逻辑下降路径。
最小验证：
