为什么 MySQL InnoDB 要使用 B+ 树来存储索引？

Dear 丶 2024-02-17 10:35 29阅读 0赞

> B+Tree 中的 B 是 Balance，是平衡的意思，它在经典 B Tree 的基础上进行了优化，增加了顺序访问指针，在B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree，这样就提高了区间访问性能：如果要查询 key 为从 18 到 49 的所有数据记录，当找到 18 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率（无需返回上层父节点重复遍历查找减少 IO 操作）。  
> 索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上，这样的话，索引查找过程中就要产生磁盘 IO 消耗，相对于内存存取，IO 存取的消耗要高几个数量级，所以索引的结构组织要尽量减少查找过程中磁盘 IO 的存取次数，从而提升索引效率。  
> 综上所述，InnDB 只有采取 B+ 树的数据结构存储索引，才能提供数据库整体的操作性能。

MySQL InnoDB存储引擎选择使用B+树来存储索引，主要基于以下几个原因：

1.  范围查询和排序性能：B+树在范围查询和排序操作上具有优势。B+树的所有叶子节点通过链表连接成有序序列，这使得范围查询和顺序访问更加高效。B+树的叶子节点包含了完整的数据记录，因此在范围查询时可以直接遍历叶子节点的链表，避免不必要的磁盘I/O操作。相比之下，B树的非叶子节点也存储了部分数据记录，范围查询需要进行更多的磁盘I/O操作。
2.  磁盘块访问和预读性能：B+树通过使用较大的数据块（通常是页）来减少磁盘I/O操作。B+树中的节点尽可能填满一个磁盘块，这样在查询时可以更有效地利用磁盘预读的能力，提高查询性能。相比之下，B树由于非叶子节点也存储了数据记录，每个节点的利用率较低，磁盘I/O开销相对较高。
3.  磁盘空间利用率：B+树索引相对节约磁盘空间。B+树的内部节点仅存储键值和指针，而叶子节点存储了全部数据和指针。这样的结构使得B+树能够更好地利用磁盘空间，减少存储开销。相比之下，B树的非叶子节点也存储了数据记录，占用了额外的磁盘空间。
4.  并发性和事务处理：B+树索引适用于并发访问和事务处理。B+树的结构特性使得在并发访问时更容易实现锁机制和保持数据的一致性。另外，InnoDB存储引擎使用MVCC（多版本并发控制）来支持高并发事务，B+树结构更适合支持MVCC机制。

综上所述，MySQL InnoDB存储引擎选择使用B+树来存储索引，是因为B+树在范围查询和排序性能、磁盘块访问和预读性能、磁盘空间利用率以及并发性和事务处理方面具有优势，能够更好地满足数据库的查询和事务处理需求。