Java面试复习 Day 4

今日任务

一、B+树 vs B树 vs 二叉树

这三种都是常见的树形数据结构，核心差异体现在分支数量、存储逻辑和适用场景上，下面从基础定义、核心特性和适用场景三个维度展开对比。

1.基础定义

二叉树‌

二叉树是最基础的树形结构，规则非常简单：每个节点最多只能有2个子节点，左子树存储小于当前节点的值，右子树存储大于当前节点的值。它是所有树结构的入门原型，但普通二叉查找树在顺序插入连续数据时，很容易退化成链表，查询效率直接降到O(n)。

‌B树（多路平衡查找树）‌

B树是专门为磁盘存储设计的“矮胖型”多叉树，打破了二叉树最多2个分支的限制，单个节点可以支持几十甚至上百个子节点。它的核心规则是所有节点（包括内部节点和叶子节点）都会同时存储索引关键字和真实数据，整棵树的所有叶子节点都处于同一层，天然保持平衡。

B+树‌

B+树是B树的优化变种，是目前数据库索引的主流实现方案。它把索引和数据完全分离：非叶子节点只存储索引关键字，不存任何真实数据，只有最底层的叶子节点才会存储完整数据，且所有叶子节点通过双向链表按顺序串联起来，天然支持有序遍历。

2.核心特性对比

3.适用场景总结

• 二叉树‌：仅适合教学入门学习，生产环境几乎不会直接使用，只有经过平衡优化的红黑树等变种，会用于Java的HashMap等内存场景，完全不适合磁盘数据库做索引。
• ‌B树‌：属于过渡型的磁盘索引结构，相比二叉树大幅减少了磁盘IO次数，但因为范围查询效率低，现在已经很少在主流数据库中作为主索引使用，部分旧文件系统会采用该结构。
• ‌B+树‌：是当前数据库和文件系统的首选索引结构，MySQL InnoDB的聚簇索引、NTFS等文件系统的目录管理，几乎全部基于B+树实现，完美适配大数据量下的高效范围查询、排序和分页场景。

二、B+树 vs B树 vs 二叉树：为什么MySQL选B+树

MySQL选择B+树作为其索引结构的主要原因是B+树在多种数据库和存储系统中提供了高效的查询性能、范围查询能力和磁盘I/O效率。下面是B+树相对于其他数据结构（如二叉树和B树）的几个主要优势：

1. 磁盘I/O效率

B+树的内部节点不存储数据，只存储键值，这使得每个节点可以存储更多的键值对，从而减少了树的深度，减少了磁盘I/O操作的次数。相比之下，二叉树在最坏的情况下会退化成链表，导致查询效率非常低；而B树虽然可以减少树的深度，但由于其内部节点也存储数据，可能导致单个节点存储的数据量较小，从而增加磁盘I/O操作。

2. 范围查询

B+树的叶子节点之间通过指针相连，形成一个有序链表。这使得范围查询非常高效，因为你可以直接从链表的开始遍历到结束，而不需要像在B树中那样回溯到根节点。这在执行如`SELECT * FROM table WHERE key BETWEEN A AND B`这样的查询时特别有用。

3. 插入和删除操作

B+树的插入和删除操作通常只需要重新平衡树的一部分，而不是整个树。这是因为B+树的分裂和合并操作主要发生在叶子节点上，而内部节点主要负责维护键的平衡。这种局部性的特性减少了这些操作的成本。

4. 顺序访问

由于叶子节点之间通过指针相连，B+树支持非常高效的顺序访问。这对于某些类型的数据库操作（如全表扫描、排序操作等）特别有用。

5. 内存和磁盘的适配

B+树的设计考虑到了内存和磁盘存储之间的差异。通过减少内部节点的数据存储和增加叶子节点的数据存储，B+树优化了数据在磁盘上的布局，使得每次磁盘I/O操作能够更有效地利用缓存和预取技术。

总结
综上所述，B+树因其高效的磁盘I/O、范围查询能力、局部性的插入和删除操作、以及优化的内存和磁盘存储适配性，成为了MySQL等数据库系统中广泛使用的索引结构。相比之下，虽然二叉树简单但效率低下，而纯B树虽然在某些方面优于二叉树，但由于其内部节点也存储数据，可能在某些情况下不如B+树高效。因此，B+树因其综合性能优势成为了数据库索引的首选。

三、聚簇索引 vs 非聚簇索引（回表/覆盖索引）

聚簇索引和非聚簇索引是MySQL InnoDB引擎的核心索引类型，二者最核心的差异是数据存储位置不同，还衍生出了回表、覆盖索引这类关键特性。

1.基础定义与存储结构

1. ‌聚簇索引‌
   聚簇索引的索引结构和完整行数据绑定在一起，B+树的叶子节点直接存储整行数据，查到索引就等于拿到了全部数据。
   在InnoDB中，它的生成规则是：优先使用表的主键作为聚簇索引；没有主键时选第一个非空唯一索引；都没有时会自动生成一个6字节的隐式row_id作为聚簇索引。一个表‌只能有1个聚簇索引‌，它直接决定了数据在磁盘上的物理排列顺序。

2. ‌非聚簇索引‌
   非聚簇索引也叫二级索引，它的索引结构和行数据完全分离，B+树的叶子节点只存储索引列的值和对应的聚簇索引主键值，不会存放完整行数据。
   一个表可以创建‌多个非聚簇索引‌，不同的非聚簇索引各自维护独立的B+树结构，数据行在磁盘上是乱序存放的。

2.核心特性：回表操作与覆盖索引

1. ‌回表操作‌
   通过非聚簇索引查询非索引字段时，会触发“回表”：第一步先在非聚簇索引的B+树中检索，拿到对应的主键值；第二步拿着这个主键，再去聚簇索引的B+树中查询一次，最终拿到完整的行数据。这个过程多了一次随机磁盘IO，查询性能会明显低于直接走聚簇索引的查询。

2. ‌覆盖索引‌
   如果你的查询语句里，所有需要返回的字段都刚好是非聚簇索引的索引列（比如SELECT id,name FROM users WHERE name='张三'，且name是普通索引），此时不需要拿到完整行数据，直接从非聚簇索引的叶子节点就能获取全部所需信息，就可以避免回表，这种场景就叫做覆盖索引，性能能接近聚簇索引的查询效率。

3.核心差异对比

4实际使用建议

• 主键优先选择短整型自增ID，用UUID这类随机字符串做主键，会频繁触发页分裂，导致聚簇索引产生大量磁盘碎片，严重影响性能。
• 不要创建过多非聚簇索引，每新增一个二级索引，都会大幅增加表的写入开销，只为高频查询场景建立非聚簇索引更划算。
• 针对高频的非主键查询，尽量设计覆盖索引，避免不必要的回表操作，能大幅提升查询效率。

四、最左匹配原则：用联合索引(a,b,c)举例，哪些查询走索引，哪些不走

在 MySQL 中，联合索引(a, b, c)遵循‌最左前缀原则（Leftmost Prefix Rule）‌。这意味着查询条件必须从索引的最左边字段a开始匹配，且不能跳过中间的字段，直到遇到范围查询为止。

1.✅ 能走索引的情况

只要查询条件包含了索引的‌连续前导列‌，就能利用索引进行快速查找。

2.❌ 不走索引（或索引失效）的情况

如果查询条件‌跳过了最左列‌，或者‌最左列未出现在条件中‌，则无法利用该联合索引进行定位，通常会退化为全表扫描（除非触发覆盖索引，见下文特殊情况）。

3.⚠️ 特殊规则：范围查询截断

‌核心规则：‌ 一旦在联合索引中遇到‌范围查询‌（>,<,>=,<=,BETWEEN,LIKE 'abc%'），该列右边的后续列将‌无法再利用索引进行排序或查找‌。

4.💡 特殊情况：覆盖索引（Covering Index）

即使查询条件不符合最左前缀原则（如只查b, c），如果SELECT的字段‌全部包含在索引中‌，MySQL 可能会选择‌覆盖索引‌扫描，从而避免回表，但这本质上还是扫描了索引树，而非通过索引“定位”数据。

• ‌场景：‌SELECT a, b, c FROM table WHERE b = 2 AND c = 3;
• ‌分析：‌ 虽然WHERE条件跳过了a，理论上不能通过索引快速定位。但如果 MySQL 优化器判断扫描整个二级索引比回表查聚簇索引更快（例如数据量小或索引较小），它可能会执行Index Scan。
• ‌注意：‌ 这在EXPLAIN中通常显示为Using index，但这与传统的“通过索引快速定位少量记录”不同，性能差异巨大。‌一般讨论“走索引”时，主要指能否通过索引快速定位（Seek），此时b=2 AND c=3仍视为不走索引定位。

总结：

1. ‌最左优先：‌ 必须从a开始。
2. ‌连续匹配：‌ 中间不能断（如a有，b无，c有，则c失效）。
3. ‌范围截断：‌ 遇到>、<、BETWEEN、LIKE前缀模糊匹配，后面的列索引失效。
4. ‌顺序无关：‌WHERE子句中字段的书写顺序不影响索引命中，MySQL 优化器会自动调整。

‌最佳实践建议：‌
在设计联合索引时，应将‌等值查询‌的字段放在前面，‌范围查询‌的字段放在最后。例如，如果查询常为WHERE a = ? AND b = ? AND c > ?，则索引(a, b, c)是最优解。