罗罗编程学习记录
本页内容 展开查看

05.1.1.1 B+ 树与索引结构

所属:全栈开发面试题库 / 05 数据库与存储 / 05.1 关系型数据库通用能力 / 05.1.1 索引原理与设计

覆盖范围

  • 磁盘页与随机/顺序 I/O 的概念
  • B+ 树节点存储分工、扇出、树高与容量估算
  • 聚簇索引与二级索引的组织差异
  • 主键选择、页分裂与碎片
  • 哈希索引、自适应哈希索引、NULL 与大字段索引边界
  • MySQL InnoDB 与 PostgreSQL 堆表组织差异

高频题速览

编号 题目 难度 频率
05.1.1.1-001 为什么用 B+ 树而不是 B 树、哈希或红黑树 进阶 ★★★★★
05.1.1.1-002 数据库为什么按页读取 基础 ★★★★★
05.1.1.1-003 B+ 树非叶子与叶子各存什么 进阶 ★★★★★
05.1.1.1-007 聚簇索引与非聚簇索引区别 进阶 ★★★★★

索引结构主线

表数据按页(InnoDB 默认 16KB)组织
  → B+ 树:非叶子只存 key + 子页指针(扇出大、树高低)
  → 叶子:InnoDB 聚簇索引存整行;二级索引存索引列 + 主键
  → 叶子之间双向链表,支持范围扫描与有序遍历

05.1.1.1-001 为什么 MySQL 用 B+ 树,而不是 B 树、哈希索引或红黑树?

频率 ★★★★★ | 难度 进阶

一句话结论

磁盘按页读取,索引设计的目标是减少随机 I/O 次数;B+ 树非叶子只存键、扇出大树高低,叶子有序链表支持范围扫描与排序,所有查询路径等长,因此成为关系库主键索引的主流结构。

概念解释

  • 红黑树:二叉结构高度约 log2(N),2000 万行约 24 层,每层可能一次随机 I/O,磁盘场景不可接受。
  • B 树:非叶子也存数据,单页能放的键与指针变少、扇出小、树更高;范围查询需要在树中反复回溯。
  • 哈希:等值查询 O(1),但不支持范围、排序与最左前缀,哈希冲突严重时退化。
  • B+ 树:非叶子只存键,扇出大;叶子有序链表,范围扫描与 ORDER BY 高效;所有数据都在叶子,查询路径长度一致。

原理流程

  1. 磁盘读取以页为单位,一次 I/O 取回整页,索引评估的核心是"树高 = 随机 I/O 次数"。
  2. 非叶子节点只做路由,不携带整行数据,单页可容纳成百上千个键指针。
  3. 叶子页按键有序并用双向链表串联,范围查询沿链表顺序扫描,避免反复回到树中查找。

代码 / 命令

结构对比:
  红黑树  高度 log2(N),2000 万行 ≈ 24 层
  B 树    非叶子存数据,扇出受限,范围查询需回溯
  哈希    等值 O(1),无范围/排序/前缀能力
  B+ 树   非叶子存键,3 层可覆盖千万级,叶子链表支持范围扫描

常见误区

  • 误区:B+ 树快是因为比较次数少。正解:主要收益是降低磁盘随机 I/O 次数(树高低),CPU 比较次数不是瓶颈。
  • 误区:哈希索引在数据库里完全没用。正解:内存表、自适应哈希与缓存系统中哈希仍是等值查询的首选结构,只是不适合作为通用磁盘索引。

追问

  • 问:为什么 B 树非叶子存数据会降低扇出?答:每条记录占用空间大,单页能存放的键与指针变少,同样数据量需要更多层。
  • 问:B+ 树叶子链表对排序有什么帮助?答:叶子按键有序,ORDER BY 命中索引顺序时可直接沿链表输出,避免额外 filesort。

05.1.1.1-002 数据库为什么按页读取?页大小对索引有什么影响?

频率 ★★★★★ | 难度 基础

一句话结论

磁盘随机寻道成本远高于顺序传输,数据库把数据按固定大小的页(InnoDB 默认 16KB)组织,一次 I/O 取回整页,相邻记录可以一起被访问;页大小直接影响扇出、树高与缓冲池利用率。

概念解释

  • 页(page):磁盘与内存管理数据的最小单位,InnoDB 默认 16KB,PostgreSQL 默认 8KB(版本与配置相关,以当前实例为准)。
  • 随机 I/O 与顺序 I/O:随机寻道慢,页内顺序读取成本低,因此数据库尽量把相关记录放在同一页。
  • 缓冲池(Buffer Pool):热点页缓存在内存,命中则不读盘;页是缓冲池管理的单位。

原理流程

  1. 访问记录时先查缓冲池,未命中则从磁盘按页加载。
  2. 同一页内的后续记录被顺带读出,范围扫描局部性好。
  3. 索引页与数据页都按页管理,页填满后分裂出新页。

代码 / 命令

-- MySQL:查看页大小(只读参数)
SHOW VARIABLES LIKE 'innodb_page_size';

-- PostgreSQL:查看块大小
SHOW block_size;

常见误区

  • 误区:把行大小和页大小混为一谈。正解:一行只是页内的一条记录,一页可存放多行;行越大,单页行数越少。
  • 误区:页越大越好。正解:页过大时缓冲池能缓存的页数减少、扫描浪费增加;页过小则树更高,需按负载权衡。

追问

  • 问:页大小能在线修改吗?答:不能直接改已有表,需重建表/实例;MySQL 修改 innodb_page_size 需初始化数据目录,具体行为以版本文档为准(待确认)。
  • 问:为什么随机主键会降低页内利用率?答:随机插入分散到不同页,很多页只写入少量记录就被缓存,碎片率上升。

05.1.1.1-003 B+ 树非叶子节点和叶子节点分别存什么?

频率 ★★★★★ | 难度 进阶

一句话结论

非叶子节点只存索引键与子页指针,用于路由定位;叶子节点存实际数据(聚簇索引)或索引键加主键值(二级索引),并通过双向链表相连。

概念解释

  • 非叶子(内部节点):保存键的副本与指向子节点的页指针,不存放整行,因此单页扇出大。
  • 叶子节点:索引的最底层,数据按键有序排列;聚簇索引叶子即数据行,二级索引叶子是索引项。
  • 链表:叶子页之间双向连接,支持从任意起点向前/向后范围扫描。

原理流程

  1. 从根节点开始,用目标键在非叶子页中二分定位下一层指针。
  2. 逐层向下直到叶子页,在页内二分或顺序查找目标记录。
  3. 范围查询定位起点叶子后,沿链表向后扫描直到不满足条件。

代码 / 命令

非叶子页:[key1 | ptr1] [key2 | ptr2] ...  (键 + 指针)
叶子页:  [索引项/整行] ↔ [索引项/整行] ↔ ...  (有序 + 双向链表)

常见误区

  • 误区:非叶子节点也缓存整行数据。正解:非叶子只存路由键与指针,整行只在聚簇索引叶子。
  • 误区:二级索引叶子存物理行地址。正解:InnoDB 二级索引叶子存索引列加主键值,回表时再用主键查聚簇索引;MyISAM 才存行地址。

追问

  • 问:为什么非叶子只存键能降低树高?答:索引项占用空间小,单页可放成百上千个指针,扇出大,层数随之减少。
  • 问:根节点为什么常驻留内存?答:每次查询都从根开始,根与上层节点访问频率最高,缓冲池优先保留它们。

05.1.1.1-004 B+ 树有几层?一张表大概能存多少行?

频率 ★★★☆☆ | 难度 进阶

一句话结论

以 InnoDB 16KB 页、主键 BIGINT(8 字节)加 6 字节页指针估算,非叶子单页约可放千余个指针,三层 B+ 树即可支撑千万级行,通常不需要到四层。

概念解释

  • 扇出:一个非叶子页能指向的子页数量,决定每层放大倍数。
  • 叶子行数:由行长度决定,行越大单页行数越少。
  • 树高:数据量增长到下一级页放不下时才增加一层,根节点与上层常驻内存。

原理流程

  1. 估算非叶子单页索引项大小(键长 + 指针),得到单页指针数。
  2. 按叶子单页行数估算每层承载量:两层为扇出 × 单页行数,三层再乘一次扇出。
  3. 结合实际行长度与索引宽度复核,行越宽树越高。

代码 / 命令

估算(16KB 页,BIGINT 主键 + 6 字节指针):
  非叶子单页 ≈ 16KB / 14B ≈ 1170 个指针
  叶子每行 1KB ≈ 16 行/页
  两层:1170 × 16 ≈ 1.8 万行
  三层:1170 × 1170 × 16 ≈ 2100 万行
  四层:约百亿级,通常不需要

常见误区

  • 误区:树高固定为三层。正解:树高随行宽、索引宽度与数据量变化,上述数字只是典型估算。
  • 误区:主键越长不影响二级索引体积。正解:二级索引叶子都冗余存主键,主键变长会让所有二级索引一起变大。

追问

  • 问:行越大树越高吗?答:叶子单页可放行数变少,同样数据量需要更多叶子页,树可能增加一层。
  • 问:实际磁盘 I/O 次数一定等于树高吗?答:不一定,根与中层节点常驻缓冲池时,一次查询往往只有叶子页需要读盘。

05.1.1.1-005 扇出是什么?如何估算单页能放多少索引项?

频率 ★★★☆☆ | 难度 进阶

一句话结论

扇出指一个非叶子节点能指向的子节点数量,由页大小除以单个索引项(键长加指针长度)决定;扇出越大,相同数据量下树越矮。

概念解释

  • 索引项大小:键本身占用字节数加页指针长度;变长键还需考虑长度标记。
  • 扇出估算:页大小 / 单索引项字节数,得到单页可容纳的指针数量。
  • 影响因素:主键类型、索引列数量与类型、是否包含大字段,都会改变索引项宽度。

原理流程

  1. 统计索引列总字节数,加上指针与开销字段。
  2. 用页大小除以单项大小得到单页索引项数。
  3. 用扇出连乘估算各层承载量,判断是否需要增加树层。

代码 / 命令

扇出 ≈ innodb_page_size / (索引键字节数 + 页指针字节数 + 开销)
例:16384B / (8B 主键 + 6B 指针) ≈ 1170

常见误区

  • 误区:扇出只由页大小决定。正解:键越长扇出越小,宽主键、多列联合索引都会压低扇出。
  • 误区:估算结果可以精确到个位数。正解:页内还有目录项、碎片与填充因子,估算只用于量级判断。

追问

  • 问:为什么要用短主键?答:短主键缩小二级索引叶子项宽度,提高所有二级索引扇出并减少空间占用。
  • 问:联合索引项比单列索引宽多少?答:项宽为各列宽度之和,多列联合索引的非叶子与叶子项都更宽,扇出相应下降。

05.1.1.1-006 叶子节点的双向链表带来什么能力?

频率 ★★★★☆ | 难度 基础

一句话结论

叶子页按键有序并双向串联,使范围扫描、有序输出和反向遍历可以沿链表顺序进行,不必反复回到树中查找;这也是索引能辅助 ORDER BY 的结构基础。

概念解释

  • 顺序扫描:定位起始叶子后,沿链表向后读取相邻页,局部性好。
  • 双向:支持向前与向后遍历,可服务正序、倒序输出(倒序索引另见 05.1.1.2)。
  • 有序性:页内按键排序,页间链表也按键有序,整条叶子链是一个有序序列。

原理流程

  1. 等值或范围条件先定位到起始叶子页。
  2. 命中记录后沿链表读取后续页,直到键超出范围。
  3. 输出顺序与索引顺序一致,若与 ORDER BY 方向匹配则可免排序。

代码 / 命令

叶子链:[1|3|5] ↔ [7|9|11] ↔ [13|15|17]
范围查询 key BETWEEN 4 AND 12:从 5 所在页起,沿链读到 11 为止

常见误区

  • 误区:链表只在叶子内部、跨页没有链接。正解:跨叶子页之间同样有双向指针,范围扫描可跨页连续进行。
  • 误区:有链表就一定不用排序。正解:只有排序列顺序、方向与索引匹配时才能免 filesort,条件不满足仍需额外排序。

追问

  • 问:范围扫描为什么比多次单点查找快?答:沿链表是顺序读取相邻页,减少随机寻道;回表随机读则另当别论。
  • 问:插入新键后链表如何保持有序?答:新记录落到对应叶子页,页满时分裂,链表指针在分裂后重新衔接。

05.1.1.1-007 聚簇索引和非聚簇索引有什么区别?

频率 ★★★★★ | 难度 进阶

一句话结论

聚簇索引叶子直接存放整行数据,一张表只有一个;二级(非聚簇)索引叶子存索引列加主键值,查询非索引列时需要回表。

概念解释

维度 聚簇索引(Clustered) 二级索引(Secondary)
叶子内容 整行数据 索引列 + 主键值(InnoDB)
数量 每表一个 可有多个
查询 主键查询直接取整行 可能需要回表
存储顺序 数据按主键物理有序 按索引列有序
  • InnoDB 有主键则主键索引即聚簇索引;无主键则选第一个非空唯一索引;都没有则生成隐藏 ROW_ID。
  • MyISAM 是堆表结构,索引与数据分离,主键与二级索引叶子都存行地址,没有聚簇索引。

原理流程

  1. 聚簇索引按主键组织数据物理顺序,插入顺序影响页分裂与碎片。
  2. 二级索引独立成树,叶子记录索引键与对应主键。
  3. 二级索引查询拿到主键后,再进入聚簇索引取整行,即回表。

代码 / 命令

-- 主键(聚簇索引):直接定位整行
SELECT * FROM users WHERE id = 1001;

-- 二级索引:先在索引树找到 id,再回聚簇索引取行
SELECT * FROM users WHERE name = 'Ann';

常见误区

  • 误区:一张表可以建多个聚簇索引。正解:数据物理上只能按一种顺序组织,聚簇索引每表一个。
  • 误区:二级索引叶子存的是行号。正解:InnoDB 存主键值;MyISAM 才存行地址,PostgreSQL 索引存元组标识(TID)。

追问

  • 问:为什么二级索引存主键而不是行地址?答:聚簇索引重组后行位置会变,存主键更稳定,也使覆盖索引可以直接从二级索引取列。
  • 问:没有主键的表有什么问题?答:依赖隐藏 ROW_ID 全局递增,高并发插入可能形成右侧热点,且二级索引项更大。

05.1.1.1-008 InnoDB 没有主键时聚簇索引怎么来?

频率 ★★★★☆ | 难度 进阶

一句话结论

优先使用主键作为聚簇索引;没有主键时选第一个非空唯一索引;两者都没有,InnoDB 生成隐藏的 6 字节 ROW_ID 作为聚簇键。

概念解释

  • 主键优先:显式 PRIMARY KEY 直接成为聚簇索引键。
  • 唯一索引兜底:存在非空唯一索引时,按定义顺序选第一个作为聚簇键。
  • 隐藏 ROW_ID:无合适键时系统内部生成递增行 ID,用户不可见。

原理流程

  1. 建表时检查是否定义主键。
  2. 无主键则扫描非空唯一索引,取第一个。
  3. 都不存在则使用内部 ROW_ID 组织聚簇树。

代码 / 命令

-- 推荐:显式主键
CREATE TABLE users (
  id BIGINT PRIMARY KEY,
  name VARCHAR(64)
);

-- 不推荐:无主键、唯一索引允许 NULL,可能落到隐藏 ROW_ID
CREATE TABLE orders (
  order_no VARCHAR(32) UNIQUE NULL,
  amount DECIMAL(10,2)
);

常见误区

  • 误区:唯一索引即使允许 NULL 也能当聚簇键。正解:只有非空唯一索引才会被选为兜底聚簇键。
  • 误区:隐藏 ROW_ID 对业务可见可查。正解:它是内部字段,用户不能直接引用,也无法通过它优化索引。

追问

  • 问:用隐藏 ROW_ID 有什么隐患?答:全局递增导致插入集中到右侧叶子页,高并发下产生热点;二级索引也冗余该隐藏键。
  • 问:怎么检查表有没有主键?答:查 information_schema.STATISTICS 或 SHOW INDEX,确认存在 Key_name = PRIMARY 的索引。

05.1.1.1-009 二级索引叶子为什么存主键而不是行地址?

频率 ★★★★☆ | 难度 进阶

一句话结论

聚簇索引重组(页分裂、重建)会改变行的物理位置,存主键这种逻辑标识比存物理行地址更稳定;同时覆盖索引可以直接从二级索引返回需要的列,无需回表。

概念解释

  • 逻辑标识:主键在行移动后保持不变,二级索引项不需要随之改写。
  • 回表路径:二级索引给出主键,再到聚簇索引按主键取行,路径确定。
  • 覆盖基础:若查询列都在二级索引中,叶子项已包含所需值,可直接返回。

原理流程

  1. 插入行时聚簇树按主键落位,二级索引叶子记录索引键与主键。
  2. 聚簇页分裂或重建只移动数据行,二级索引项中的主键仍有效。
  3. 查询时按主键回聚簇索引定位最新位置。

代码 / 命令

二级索引叶子项:(索引列值, 主键值)
回表:索引列 → 主键值 → 聚簇索引叶子 → 整行

常见误区

  • 误区:二级索引存物理偏移量,行移动后索引自动更新。正解:InnoDB 选择主键作为稳定标识;物理位置变化不会破坏二级索引项。
  • 误区:主键宽度不影响二级索引。正解:主键被冗余进每个二级索引叶子,主键越长所有二级索引体积越大。

追问

  • 问:PostgreSQL 索引叶子存什么?答:存元组标识(TID,页号 + 行号),堆表不聚簇;HOT 更新与索引维护机制与 InnoDB 不同,详见 05.3.1。
  • 问:主键选宽类型有什么连锁代价?答:所有二级索引项变宽,扇出下降、空间占用与写入放大同时上升。

05.1.1.1-010 MyISAM 与 InnoDB 的索引数据组织有何不同?

频率 ★★★☆☆ | 难度 进阶

一句话结论

MyISAM 是堆表,数据与索引分离,主键和二级索引叶子都存行地址;InnoDB 是索引组织表,数据按聚簇主键排列,二级索引叶子存主键。

概念解释

  • 堆表:数据按插入顺序堆放,不按索引键物理排序。
  • 索引组织表(IOT):数据本身就是聚簇 B+ 树的叶子。
  • 行地址 vs 主键:MyISAM 索引指向数据文件中的行位置;InnoDB 二级索引指向主键。

原理流程

  1. MyISAM 查询先在索引文件定位行地址,再到数据文件取行。
  2. InnoDB 主键查询直接读聚簇叶子;二级索引先找主键再回聚簇树。
  3. 两者 B+ 树结构相似,差别在叶子内容与数据组织方式。

代码 / 命令

MyISAM:索引文件 → 行地址 → 数据文件
InnoDB:聚簇索引叶子 = 数据行;二级索引叶子 = (索引列, 主键)

常见误区

  • 误区:MyISAM 也有聚簇索引。正解:MyISAM 索引与数据分离,不存在聚簇组织。
  • 误区:两种引擎的回表概念完全相同。正解:MyISAM 按行地址取数据;InnoDB 按主键回聚簇索引,多一次 B+ 树查找。

追问

  • 问:为什么新业务默认都用 InnoDB?答:InnoDB 支持事务、行锁、MVCC 与崩溃恢复;MyISAM 只适合只读归档等边缘场景。
  • 问:InnoDB 聚簇组织对范围查询有什么好处?答:数据按主键有序,范围查询沿叶子链表顺序读取,相邻行物理相邻。

05.1.1.1-011 PostgreSQL 的索引为什么没有聚簇索引概念?

频率 ★★★☆☆ | 难度 进阶

一句话结论

PostgreSQL 采用堆表组织,行版本与索引分离,索引叶子存元组标识(TID),数据行不按某个索引键物理排序;CLUSTER 命令只能一次性按索引物理重排,后续更新会逐渐失效,不是持续维护的聚簇索引。

概念解释

  • 堆表:行存放在无序堆中,更新产生新版本,由 vacuum 回收。
  • TID:索引项记录页号与行号,回堆表取整行。
  • CLUSTER:按某个索引一次性重排物理顺序,不随写入自动维护。

原理流程

  1. 索引扫描在索引树中收集命中 TID。
  2. 按 TID 回堆表取行;位图索引扫描会先合并位图再批量回堆。
  3. 数据物理顺序不绑定任何索引,因此没有"聚簇索引"。

代码 / 命令

-- PostgreSQL:查看索引定义(索引存 TID,堆表组织)
SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'users';

-- 一次性按索引物理重排(不自动持续维护)
CLUSTER users USING users_pkey;

常见误区

  • 误区:PostgreSQL 没有主键索引。正解:有主键 B-tree 索引,只是数据不按它聚簇存储。
  • 误区:CLUSTER 之后数据库会持续保持有序。正解:后续增删改会破坏物理顺序,需要重新 CLUSTER 或用填充因子等手段缓解。

追问

  • 问:PG 回表与 InnoDB 回表有何不同?答:PG 按 TID 回堆,InnoDB 按主键回聚簇树;HOT 更新可避免索引膨胀。
  • 问:堆表组织在什么场景吃亏?答:大范围按主键顺序扫描时,物理顺序不连续可能增加随机访问;具体性能以实测为准。

05.1.1.1-012 主键用自增 ID 还是 UUID?

频率 ★★★★☆ | 难度 进阶

一句话结论

单库或有统一发号器的场景优先用 BIGINT 自增或 Snowflake,顺序写、索引紧凑;UUID v4 随机导致页分裂与缓存命中率差,需要全局唯一时优先选时间有序的 UUID v7 或 ULID。

概念解释

维度 自增 BIGINT UUID(36 字符)
存储 8 字节 36 字符,二级索引全量冗余
顺序 递增,顺序写 随机,页分裂
分库分表 需发号器 天然全局唯一
可猜测 是,需防遍历 否
索引效率 高 低,碎片与缓存命中差

原理流程

  1. 评估是否需要跨库全局唯一:单库自增即可,分布式需发号器。
  2. 选择键类型:短而有序优先 BIGINT;必须随机不可猜再考虑有序 UUID。
  3. 校验索引体积与写入模式,避免宽随机键进聚簇索引。

代码 / 命令

-- 自增主键(MySQL)
id BIGINT PRIMARY KEY AUTO_INCREMENT

-- 时间有序 UUID(MySQL 8.0 可生成 v1 风格,v7 支持情况待确认以版本文档为准)
-- 不推荐:随机 UUID 作为聚簇主键
id CHAR(36) PRIMARY KEY

常见误区

  • 误区:UUID 全局唯一就适合做主键。正解:唯一性与聚簇写入效率是两件事;随机 UUID 作为聚簇键会显著放大页分裂。
  • 误区:自增 ID 绝对安全。正解:自增值可被遍历,敏感业务需在应用层做权限控制或对外使用不可猜的业务 ID。

追问

  • 问:UUID v7 相比 v4 好在哪里?答:v7 内嵌时间戳前缀,值大致按时间有序,插入更接近顺序写,仍保留全局唯一性。
  • 问:Snowflake ID 的结构是什么?答:时间戳 + 机器位 + 序列号,趋势递增,需协调机器位避免冲突;发号细节见 05.1.4.2。

05.1.1.1-013 为什么自增主键能减少页分裂?

频率 ★★★★☆ | 难度 高级

一句话结论

聚簇索引按主键有序组织,自增值总是追加到最右侧叶子页,属于顺序写入;随机主键插入到中间页,页满时触发分裂,带来写入放大、碎片率上升与二级索引连带随机化。

概念解释

  • 顺序追加:新行落到当前最右叶子页,页未满则直接追加。
  • 页分裂:目标页已满时拆成两个页,搬运约一半数据,写入量放大。
  • 碎片:分裂后页利用率下降,随机插入反复发生时空间利用率可能只有一半左右。

原理流程

  1. 自增主键:新值大于已有最大值,定位最右叶子页追加。
  2. 随机主键:新值落在某个中间区间,对应页已满则分裂。
  3. 分裂产生新页并调整链表指针,二级索引同样按随机键写入。

代码 / 命令

自增:[1 2 3 4 5] → [1 2 3 4 5 6 7]        右侧追加,顺序写
UUID:[a c e g i] 插入 b → 页满分裂 → [a b] [c e g i]

常见误区

  • 误区:页分裂只影响聚簇索引。正解:二级索引同样按各自键组织,随机主键或随机二级键都会在对应树上产生分裂。
  • 误区:分裂后页利用率会自动恢复。正解:已产生的碎片需通过重建表/索引(如 OPTIMIZE TABLE)整理,日常写入不会自动压缩。

追问

  • 问:如何整理已分裂的碎片?答:重建表或索引回收空间,大表需走在线变更流程,详见 05.1.1.5 与 05.1.4.5。
  • 问:高并发自增有什么锁竞争?答:自增分配可能涉及自增锁,MySQL 8.0 innodb_autoinc_lock_mode=2(互斥量模式)可缓解,具体行为以版本文档为准。

05.1.1.1-014 随机主键会带来哪些连带问题?

频率 ★★★☆☆ | 难度 进阶

一句话结论

随机主键除了页分裂与碎片,还会降低缓冲池局部性(热点分散)、放大二级索引随机写,并使范围扫描的物理连续性变差。

概念解释

  • 缓冲池局部性:顺序写入集中访问少量右侧页;随机写入分散到大量页,内存命中下降。
  • 二级索引连带:每个二级索引叶子都存随机主键,插入位置同样随机。
  • 范围扫描:数据物理分散,按主键范围读取时相邻记录不在同一页。

原理流程

  1. 随机键插入定位到不同中间页,页访问面扩大。
  2. 缓冲池被分散的新页占用,旧热点页更容易被淘汰。
  3. 后续范围查询需要访问更多不连续页,随机 I/O 增加。

代码 / 命令

顺序键:写入集中右侧少数页,扫描相邻页
随机键:写入分散全树,缓冲池命中下降,范围扫描随机读增多

常见误区

  • 误区:换成随机主键后只要加内存就能解决。正解:局部性是访问模式问题,加内存只能缓解峰值,不能消除分散写入。
  • 误区:随机键只影响写入。正解:读取侧的范围扫描与缓存命中率同样会受影响。

追问

  • 问:有序 UUID 是否能完全避免分裂?答:时间前缀保证大致有序,比 v4 显著改善,但同一毫秒内仍有随机部分,极端高并发下仍可能局部分裂。
  • 问:怎么判断主键导致的碎片?答:对比表空间大小与统计行数、查看页填充情况,结合插入模式与碎片指标综合判断。

05.1.1.1-015 索引本身有哪些代价?

频率 ★★★☆☆ | 难度 基础

一句话结论

索引不是越多越好:每个索引都是一棵独立 B+ 树,消耗空间,写入时需要同步维护,索引过多还会增加优化器选择成本并挤占缓冲池。

概念解释

  • 空间:二级索引冗余存储索引列与主键,占用额外表空间。
  • 写入放大:INSERT/UPDATE/DELETE 要维护所有相关索引。
  • 优化器成本:候选索引变多,计划选择的估算范围扩大,也可能选错。
  • 缓存占用:索引页占用缓冲池,挤占数据页内存。

原理流程

  1. 写入行时,聚簇索引与每个二级索引都要插入对应项。
  2. 更新索引列时,旧项删除、新项插入,产生额外 undo/redo。
  3. 高频写入表需权衡查询收益与维护成本,定期清理无用索引。

代码 / 命令

-- 查看各索引大小(MySQL,8.0 视图口径以版本为准)
SELECT index_name, stat_value
FROM information_schema.innodb_index_stats
WHERE table_name = 'orders';

常见误区

  • 误区:索引只占磁盘不占内存。正解:热点索引页同样进入缓冲池,索引过多会与数据页争用内存。
  • 误区:加索引不影响写入速度。正解:索引越多,单行写入需要维护的结构越多,写入吞吐越低。

追问

  • 问:如何发现从未被使用的索引?答:通过性能_schema 索引使用统计中读计数为 0 的索引排查,详见 05.1.1.5。
  • 问:索引维护是事务内同步完成的吗?答:是,事务提交前相关索引必须更新完成,索引故障会随事务一起回滚。

05.1.1.1-016 哈希索引和自适应哈希索引(AHI)是什么?

频率 ★★★☆☆ | 难度 进阶

一句话结论

哈希索引等值查询 O(1),但不支持范围、排序与最左前缀;InnoDB 不支持用户显式创建普通哈希索引,自适应哈希索引(AHI)由存储引擎为频繁访问的等值页自动构建。

概念解释

  • 哈希索引:按键哈希定位,结构为哈希表,Memory 引擎默认使用。
  • AHI:InnoDB 在缓冲池中对热点等值访问自动加哈希索引,减少 B+ 树查找层级。
  • 争用风险:高并发下 AHI 相关 latch 可能成为瓶颈,部分场景会选择关闭。

原理流程

  1. 引擎监测到某些 B+ 树页被高频等值访问。
  2. 在内存中为这些页构建哈希索引,键映射到页内记录。
  3. 等值查询先走哈希定位,未命中或不适用时回退 B+ 树路径。

代码 / 命令

-- MySQL:查看 AHI 开关
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';

-- AHI 相关命中与争用指标见 INNODB STATUS / performance_schema(视图口径以版本为准)
SHOW ENGINE INNODB STATUS;

常见误区

  • 误区:可以在 InnoDB 表上直接 CREATE HASH INDEX。正解:InnoDB 不支持用户显式哈希索引;可借助生成列或前缀索引,哈希能力主要由 AHI 自动提供。
  • 误区:AHI 总是开启且有益。正解:高并发写或命中率低时,AHI latch 争用可能拖慢整体,需按实测决定开关。

追问

  • 问:哈希索为什么不支持范围查询?答:哈希后的值无序,无法按键大小定位区间。
  • 问:什么场景适合手动哈希结构?答:纯等值 KV 场景用 Redis 等专用存储;关系库内等值热点由 AHI 覆盖即可。

05.1.1.1-017 索引列可以为 NULL 吗?对索引有什么影响?

频率 ★★☆☆☆ | 难度 基础

一句话结论

可以,索引会存储 NULL,IS NULL 也能走索引;但 NULL 不参与唯一去重(唯一索引允许多个 NULL),三值逻辑容易造成业务歧义,建议业务列尽量 NOT NULL DEFAULT。

概念解释

  • NULL 存储:索引项中保留 NULL 值,查询 IS NULL 可按索引定位。
  • 唯一性例外:唯一索引中多个 NULL 互不冲突。
  • 三值逻辑:NULL 与任何值比较结果都是 UNKNOWN,COUNT(col) 不统计 NULL。

原理流程

  1. 建索引时 NULL 作为普通键值进入叶子有序序列。
  2. WHERE col IS NULL 在索引中定位 NULL 区间。
  3. 唯一约束只对非 NULL 值去重,重复 NULL 允许并存。

代码 / 命令

-- 唯一索引允许多个 NULL
CREATE TABLE t (code VARCHAR(32) UNIQUE);
INSERT INTO t VALUES (NULL), (NULL);  -- 允许

-- COUNT 口径差异
SELECT COUNT(code) FROM t;   -- 不统计 NULL
SELECT COUNT(*) FROM t;      -- 统计所有行

常见误区

  • 误区:NULL 等于空字符串。正解:二者语义不同,比较、索引行为与业务含义都有区别。
  • 误区:IS NOT NULL 一定走索引。正解:能否走索引取决于 NULL 占比与优化器估算,大量非空时回表成本可能高于全表扫描。

追问

  • 问:为什么建议列定义为 NOT NULL DEFAULT?答:避免三值逻辑带来的判断遗漏,也让统计与索引行为更可预期。
  • 问:联合索引中某列为 NULL 会怎样?答:该行索引项该位置存 NULL,最左前缀判断按 NULL 规则参与;具体匹配行为以实测计划为准。

05.1.1.1-018 大字段怎么索引?全文索引的边界是什么?

频率 ★★☆☆☆ | 难度 进阶

一句话结论

TEXT/BLOB 太长无法直接建普通 B+ 树索引,可用前缀索引;全文检索用 FULLTEXT 索引与分词器,复杂相关性排序与横向扩展应外置搜索引擎,数据库只做主键回查。

概念解释

  • 前缀索引:只索引列的前 N 个字符,限制是不能用于排序/覆盖。
  • FULLTEXT:倒排式全文索引,按分词建立词到文档的映射。
  • 外置搜索:Elasticsearch/OpenSearch 承担分词、相关性与大规模检索,库内保存原始数据。

原理流程

  1. 评估大字段是否必须被等值/范围条件过滤,是则前缀索引。
  2. 关键词检索走全文索引,中文需配置分词器(MySQL ngram)。
  3. 复杂搜索场景把文档同步到外部搜索引擎,查询先查搜索系统再回库取详情。

代码 / 命令

-- 前缀索引
ALTER TABLE articles ADD INDEX idx_title_prefix (title(20));

-- MySQL 全文索引(ngram 分词)
ALTER TABLE articles ADD FULLTEXT INDEX ft_content (content) WITH PARSER ngram;
SELECT * FROM articles WHERE MATCH(content) AGAINST('数据库' IN BOOLEAN MODE);

常见误区

  • 误区:LIKE '%关键词%' 适合大文本检索。正解:前导模糊无法走 B+ 树,大表上是全表扫描。
  • 误区:数据库全文索引能替代专业搜索引擎。正解:分词质量、相关性排序、高亮、横向扩展与聚合分析能力上,外置搜索系统更完整,详见 05.5.2.3。

追问

  • 问:前缀索引能做覆盖索引吗?答:不能,索引只保存前缀,需要完整值时仍要回表。
  • 问:大字段是否适合放进联合索引?答:不建议,宽列会压低扇出、放大索引体积;应把过滤列与展示列分开考虑。

参考来源