48 | B+ 树：MySQL 数据库索引是如何实现的

B+ 树中，将叶子节点串起来的链表，是单链表还是双向链表？为什么？

在 B+树中，将叶子节点串起来的链表通常是双向链表。这是因为双向链表具有一些优势，特别是在范围查询等操作时。

以下是一些原因：

1. 支持范围查询： 双向链表允许在两个方向上轻松导航，这对于执行范围查询非常有用。如果 B+ 树的叶子节点之间使用单链表连接，那么在执行范围查询时，可能需要从头节点开始，然后沿着单链表逐个遍历节点，效率较低。

2. 简化插入和删除操作： 在双向链表中，插入和删除节点的操作更为简单，因为你可以轻松地获取前一个和后一个节点的引用。这对于 B+树这种频繁进行插入和删除操作的数据结构来说是很重要的。

3. 便于逆向遍历： 双向链表允许从尾部向头部逆向遍历，这在某些情况下是有用的。

虽然使用双向链表增加了一些额外的空间开销（每个节点需要两个指针），但考虑到上述优势，特别是在数据库系统中频繁执行范围查询的环境中，这种额外开销是可以接受的。

我们对平衡二叉查找树进行改造，将叶子节点串在链表中，就支持了按照区间来查找数据。我们在散列表（下）讲到，散列表也经常跟链表一块使用，如果我们把散列表中的结点，也用链表串起来，能否支持按照区间查找数据呢？

将散列表中的元素用链表串起来是一种常见的处理哈希冲突的方法，通常称为链地址法（Chaining）。这种方式在单个桶（bucket）中形成一个链表，具有相同哈希值的元素都存储在这个链表中。然而，这样的链表结构并不直接支持按照区间查找数据。

如果你想要支持按照区间查找数据，你可以对这个链表结构进行改造或者考虑其他的数据结构。

1. 排序链表： 将每个桶中的链表按照某种顺序（例如升序）进行排序。这样，你可以更容易地执行区间查询，从某个点开始，只需沿着链表移动到满足区间条件的节点为止。

2. 区间树： 将每个桶中的链表转化为区间树，这是一种专门设计用于支持区间查询的数据结构。区间树的结构允许高效地查找包含或与给定区间相交的所有区间。

3. 其他数据结构： 考虑其他更适合范围查询的数据结构，如跳表（Skip List）或平衡树。