真实面经题目 · 原创解析
MySQL 底层数据结构在 InnoDB 中主要围绕“页、B+树索引、聚簇索引、二级索引、Buffer Pool、事务日志”展开。真正决定查询性能的不是某一个抽象结构，而是这些结构如何协同：数据按页组织，索引以 B+树维护有序访问路径，主键索引叶子节点保存完整行记录，二级索引叶子节点保存主键值，内存中的 Buffer Pool 缓存热点页，变更再通过 redo log、undo log 等机制保证事务与崩溃恢复。理解这些内容，才能解释为什么 MySQL 不直接使用普通二叉树、红黑树或单纯哈希表作为主要索引结构。
MySQL 底层数据结构如果重点说 InnoDB，可以从存储和索引两层回答。InnoDB 的数据不是一行一行散放的，而是以页为基本单位组织，默认页大小通常是 16KB。索引层主要使用 B+树，原因是数据库面对的是磁盘和内存之间的大块 I/O，B+树高度低、分叉多、叶子节点有序并通过链表连接，适合范围查询、排序和分页。InnoDB 的主键索引是聚簇索引，叶子节点直接存放完整行数据；二级索引的叶子节点不直接存整行，而是存索引列加主键值，查询非覆盖字段时需要回表。Buffer Pool 会缓存数据页和索引页，尽量减少磁盘访问。普通二叉树或红黑树高度相对更高，磁盘随机 I/O 次数多；哈希表虽然等值查询快，但不支持范围查询、顺序扫描和排序，所以不能作为通用索引结构。
MySQL 是一个数据库系统，不同存储引擎可以有不同的底层实现。讨论常见场景时，核心通常是 InnoDB。InnoDB 把表数据、索引、事务能力和缓存机制结合在一起：磁盘上以表空间、段、区、页等层级组织数据；内存里通过 Buffer Pool 缓存数据页和索引页；查询时借助 B+树定位记录；修改时还会配合 redo log、undo log、change buffer 等机制保证一致性和性能。因此 MySQL 底层数据结构不是单一答案，最重要的主线是“页承载数据，B+树组织索引，Buffer Pool 缓解磁盘 I/O”。
InnoDB 不是每次只从磁盘读取一条记录，而是以页为基本 I/O 单位，常见默认页大小是 16KB。一个页中会保存多条行记录、页头、页目录、槽位信息以及前后页指针等元数据。页内部的记录通常按照索引键顺序组织，页目录帮助在页内做较快定位。这样设计的关键是匹配磁盘和操作系统的块式读写特性：一次 I/O 读取一批相邻数据，比频繁读取单条记录更高效。理解页之后，才能理解为什么索引节点不是只保存一个键，而是会尽量让一个节点容纳大量键值和指针。
InnoDB 索引主要使用 B+树。B+树的非叶子节点主要保存键值和子页指针，负责导航；叶子节点保存真正可访问的数据或主键引用，并且叶子节点之间按键值顺序连接。相比普通二叉树，B+树的一个节点可以容纳很多索引项，分叉数很高，树高通常很低。树高低意味着从根节点到叶子节点需要访问的页更少，磁盘随机 I/O 次数更少。叶子节点有序连接又让范围查询、ORDER BY、分页扫描、前缀匹配等场景可以顺序推进，这是哈希结构很难自然支持的。
InnoDB 表的数据本身就是按照主键索引组织的，这个主键索引称为聚簇索引。聚簇索引的叶子节点保存完整行记录，因此通过主键查询时，沿着 B+树找到叶子页后就能直接拿到整行数据。如果表显式定义了主键，InnoDB 会使用该主键作为聚簇索引；如果没有合适主键，会选择唯一非空索引或内部隐藏标识。聚簇索引让主键查询非常高效，但也意味着主键选择会影响数据物理组织。过长、随机、频繁变更的主键可能增加页分裂、空间浪费和二级索引体积。
二级索引也是 B+树，但它的叶子节点通常不保存完整行数据，而是保存二级索引列和对应的主键值。通过二级索引查询时，如果所需字段都在该索引中，就可以形成覆盖索引，直接返回结果；如果还需要其他字段，就要先在二级索引中找到主键值，再回到聚簇索引中按主键查完整行，这个过程通常称为回表。这个设计避免了每个二级索引都重复存储完整行，节省空间并减少维护成本，但也使索引设计必须考虑选择性、覆盖字段和回表次数。
Buffer Pool 是 InnoDB 性能的关键内存结构，用来缓存数据页、索引页、undo 页等内容。查询命中 Buffer Pool 时，可以直接从内存读取页，避免昂贵的磁盘 I/O；修改数据时，通常也是先修改内存中的页，把页标记为脏页，再通过后台刷盘机制落到磁盘。Buffer Pool 内部会维护类似 LRU 的淘汰策略，并针对全表扫描等场景做优化，避免热点页被大量冷数据冲掉。很多 SQL 性能问题表面是索引问题，底层常常体现为页访问数量过多、缓存命中率低或脏页刷新压力过大。
普通二叉搜索树、AVL 树或红黑树在内存数据结构里很常见，但它们不适合作为磁盘数据库的主要索引。原因在于这些树每个节点通常只保存少量键，分叉数低，同样数量的数据会形成更高的树。数据库查一条记录往往要从根走到叶子，树越高，需要访问的页越多，随机 I/O 成本越高。B+树把一个节点设计成页级结构，一个页里放很多键和指针，从而显著降低高度。数据库优化的核心不是单次比较次数最少，而是尽可能减少磁盘页访问次数。
哈希表在等值查询中理论上很快，但它不适合作为通用索引结构。数据库大量查询不是单点等值查询，还包括范围查询、排序、分组、前缀匹配、分页扫描和最左前缀匹配。哈希表打散了键的顺序，无法高效回答“某个区间内的数据”“按索引顺序取前 N 条”这类问题。InnoDB 中存在自适应哈希索引等优化，但它是基于热点访问模式的辅助能力，不替代 B+树索引。B+树牺牲了一点理论上的单点哈希速度，换来更稳定、更通用的查询能力。
B树的非叶子节点和叶子节点都可能保存数据记录，而 B+树通常把完整数据或主键引用集中放在叶子节点，非叶子节点主要承担导航作用。这样非叶子节点可以容纳更多键和指针，树高更低，访问磁盘页更少。B+树叶子节点还天然按顺序连接，非常适合范围查询和顺序扫描。
覆盖索引指查询需要的字段都能从某个二级索引中直接得到，不需要再根据主键去聚簇索引读取完整行。因为二级索引叶子节点只保存索引列和主键值，如果查询字段超出这些内容，就会发生回表。覆盖索引的价值在于减少聚簇索引访问次数，降低随机页读取成本。
自增主键具有顺序写入特征，新记录通常追加到索引右侧，页分裂和随机插入成本相对较低。随机主键可能把新记录插入到 B+树中间位置，导致更多页分裂、页移动和缓存扰动。同时，主键值会出现在二级索引叶子节点中，主键越短，二级索引整体空间通常越小。
数据库访问磁盘页的成本远高于访问内存。Buffer Pool 缓存热点数据页和索引页，查询命中时可以避免磁盘 I/O，修改时也先在内存页上完成，再通过后台机制刷盘。索引是否合理会影响访问页数量，而 Buffer Pool 命中率决定这些页访问有多少能在内存中完成。
联合索引在 B+树中会按照多个列的组合顺序排序，例如先按第一列，再按第二列，再按第三列。只有查询条件从索引最左侧开始连续匹配时，B+树才能有效缩小搜索区间。如果跳过前导列，后续列在全局上并不是连续有序的，优化器往往无法直接利用完整索引路径。
