真实面经题目 · 原创解析
数据库索引常用 B+ 树，核心原因不是“查找复杂度看起来是 O(log n)”，而是它非常适合磁盘和页式存储：节点扇出高，树高低，单次查询需要的页访问次数少；叶子节点按键有序并通过链表连接，范围查询、排序扫描、分页扫描都很高效。二叉平衡树如 AVL、红黑树更适合内存中的动态查找结构，节点扇出低、树高大、局部性差，如果直接用于磁盘索引会产生大量随机 I/O。
数据库索引常用 B+ 树，主要是因为数据库数据通常按页存放在磁盘或 SSD 上，索引设计的目标是减少页访问次数。B+ 树是多路平衡搜索树，一个节点可以存放很多 key 和指针，所以扇出很大，几千万甚至上亿行数据也通常只需要 3 到 4 层树高。相比之下，AVL 或红黑树虽然在内存里查找很快，但每个节点通常只有两个子节点，树高会高很多，并且节点分散，容易导致大量随机 I/O。B+ 树和 B 树也有区别。B 树的内部节点和叶子节点都可以存数据；B+ 树通常只有叶子节点存完整记录或记录指针，内部节点只做导航，因此同样大小的数据页里能放更多索引键，树的扇出更高、层数更低。同时 B+ 树所有叶子节点按 key 有序连接，范围查询时定位到起点后可以顺着叶子链表连续扫描，这对数据库里的 between、order by、范围过滤、最左前缀扫描很重要。在 MySQL InnoDB 中，主键索引是聚簇索引，B+ 树叶子节点存放整行数据；二级索引的叶子节点存放二级索引 key 和主键值，查到后如果需要其他列，可能再通过主键索引回表。因此理解 B+ 树，还要理解页、扇出、树高、范围扫描、聚簇索引和二级索引这些概念。
B+ 树适合数据库索引，因为它把一次查询转化为少量页访问。它的多路结构让每层节点能容纳大量 key，树高很低；叶子节点有序并相连，范围查询效率高。二叉平衡树虽然平衡，但分叉少、树高大、磁盘局部性差，不适合做大规模磁盘索引。
数据库索引节点通常按页组织，例如一个页可能是 16KB。B+ 树内部节点只存索引键和子指针，不存完整行数据，因此一个页能容纳很多索引项，形成很大的扇出。扇出越大，树高越低，查询时需要读取的页越少。数据库索引更关心 I/O 次数，而不是单纯比较次数。
B+ 树的叶子节点保存完整有序的索引项，并通过链表连接。等值查询先从根节点定位到叶子节点；范围查询定位到起始位置后，可以沿叶子链表顺序扫描。顺序扫描比大量随机访问更适合数据库场景，因此 B+ 树天然支持范围查询、排序、分组、分页和前缀匹配。
B 树的内部节点也可能存数据，查询命中内部节点即可返回，但范围扫描不如 B+ 树顺畅。B+ 树把数据集中在叶子节点，内部节点只导航，查询路径稳定，叶子层天然有序。AVL 树和红黑树是二叉树，更适合内存结构，例如语言库中的 map 或 set；它们每层只能二分，树高远高于 B+ 树，磁盘页利用率和范围扫描能力都不如 B+ 树。
InnoDB 的主键索引是聚簇索引，叶子节点直接存整行数据，所以按主键查询可以定位到叶子节点后直接拿到行。二级索引的叶子节点通常存二级索引 key 和主键值，查询非覆盖列时需要拿主键再查一次聚簇索引，这就是回表。覆盖索引可以避免回表，因为查询需要的列已经都在二级索引里。
B+ 树主要服务于磁盘页式存储和范围扫描。内存型 key-value 系统的目标不同，常用哈希表做主键定位，并在有序集合等结构中使用跳表或其他内存友好的结构。因此不能把所有存储系统都简单归结为 B+ 树索引。
B 树的内部节点和叶子节点都可以存数据；B+ 树通常只有叶子节点存完整数据或数据指针，内部节点只负责导航。B+ 树内部节点更小，扇出更高，树高更低，并且叶子节点有序相连，更适合范围查询。
红黑树是二叉树，千万级数据会产生较高树高。数据库索引访问节点通常意味着访问磁盘页或缓冲池页，树高越高，随机页访问越多。B+ 树一个节点能容纳大量 key，树高很低，更适合页式存储。
不能脱离场景比较。在纯内存、单点查找场景下，红黑树可能很合适；在数据库磁盘索引场景下，B+ 树通过高扇出和页局部性减少 I/O，整体更合适。数据库索引优化的关键通常是页访问，而不是 CPU 比较次数。
聚簇索引的叶子节点直接存整行数据，InnoDB 中通常就是主键索引。二级索引的叶子节点存二级索引 key 和主键值。如果查询字段不在二级索引里，需要根据主键再查聚簇索引，这个过程叫回表。
如果一个查询需要的字段都能从某个二级索引中获得，就不需要回表，这个索引就覆盖了查询。覆盖索引能减少一次 B+ 树查找和额外页访问。
Redis 的主要 key 查找不是 B+ 树，而是哈希表。Redis 是内存型系统，核心目标是内存中的快速 key-value 访问。部分有序结构会使用跳表等结构。B+ 树主要适合数据库磁盘索引和页式存储场景。
