B树与B+树

B树

参考的视频为B树(B-树) - 来由, 定义, 插入, 构建

也是一种平衡搜索树，其是一种多叉平衡搜索树。

硬盘读取物理地址连续的多个字节和读取单个字节耗时几乎没有区别。

访问结点是在硬盘上进行的，结点内的数据操作是在内存中进行的。

包含数据的结点称为内部结点，下面的空结点称为外部结点(失败结点)，它们并不带任何信息，只是意味着查找失败，也叫失败结点。

称呼内部结点的最后一层为叶子结点。

B树要满足三个特性：平衡、有序、多路

平衡：B树所有的叶子结点一定在同一层

有序：结点内有序，任一元素的左子树都小于它，右子树都大于它。

对于m阶B树的结点：

最多：m个分支，m-1个元素

最少：根结点：2个分支，1个元素. 其它结点：有$\lceil \frac{m}{2} \rceil$ 个分支，$\lceil \frac{m}{2} \rceil - 1$个元素

插入

先查找到插入的位置进行插入(插入位置一定在叶结点)。如果没有出现上溢出，无需调整，否则中间元素(第$\lceil \frac{m}{2} \rceil$ 个 )上移，两边分裂(直到没有上溢出为止)

构建

依次对每个元素进行插入操作

m 阶 B 树的结点最少有：根结点：有 2 个分支，包含 1 个元素； 其他结点：有 $\lceil \frac{m}{2} \rceil$ 个分支，包含 $\lceil \frac{m}{2} \rceil - 1$ 个元素。

删除

删除非叶结点元素最终都转换成删除叶结点元素

叶结点元素：没有下溢的话，无需调整。

下溢出话，要借结点，但是注意，B树有序的性质不能被破坏。父下来，兄上去。

兄弟结点不够借的话：将其与兄弟结点合并(左右结点都可以，步骤都是父下来，兄弟结点上去)。然后对父结点检查是否其出现了下溢出。

B+树

其常被广泛用作数据库的索引结构，其本身就是一个多级的索引结构，能够加快查询速度

叶结点层包含所有元素，从小到大链接起来，通过第一个结点前的头指针

m个分支的结点有m个元素，每个元素对应子结点最大值

查找

B+树支持多种查找操作。比如：顺序查找、随机查找、范围查找

特点

1、缓存命中率高

B+树的结点通常较胖，一个结点内可以存放多个元素。让一个结点的大小尽量接近一个CPU Cache，这样当一个结点加载进缓存时，就能够获得较多信息。相比之下，红黑树是二叉树，结点瘦高，在内存中分布较为零散，访问时需要更多指针跳转。因此其缓存命中率更高。

2、范围查询的绝对优势

B+树的所有数据都存在叶子结点上，并且叶子结点之间通过一个双向链表连接，当执行查找操作时，只需要在树上定位到起始的数据，然后可以像遍历链表一样，在叶子结点进行水平遍历，这种方式非常高效。而红黑树需要进行复杂的中序遍历，访问轨迹是上下跳跃的，效率远不如B+树。

插入与删除

当一个插入操作导致某个结点的元素满了之后，执行分裂操作，中间元素(第$\lceil \frac{m}{2} \rceil$ 个 )上移，两边分裂(直到没有上溢出为止)，后面就是递归了

删除操作，当删除一个元素导致结点下溢出时，检查兄弟结点是否能借结点，但是要保持B+树的有序性质。父亲下来，兄弟结点上去。

兄弟不够借，就将其与兄弟结点合并(左右结点都可以)，然后对父结点检查其是否出现了下溢出。

插入顺序：

插入的操作是先写B+树，再写哈希表。B+树是数据存储的本体。如果B+树写入失败，返回错误。哈希表不会被污染。如果B+树成功，而哈希表失败。虽然会产生一个无法通过哈希表索引到的“幽灵数据”，但这比哈希表里有一个指针指向一个不存在的数据要好处理。

数据一致性

比如：数据在B+树里写入成功了，但写入哈希表时失败了（比如内存分配失败），这时数据不一致了怎么办？

通过固定的写入顺序来降低不一致的风险。在工业级的系统中，这个问题通常会通过预写日志（Write-Ahead Logging, WAL）来保证原子性，但我这个项目还没有实现这么复杂的机制

哈希表里存的指针直接指向B+树叶子结点中value的内存地址。当B+树结点分裂，导致数据被拷贝到新结点时，原有的指针确实会失效。

解决方法：在节点分裂或合并，即数据位置发生移动时，我需要拿到被移动数据的key，然后去更新哈希表中对应的指针，让它指向新的内存地址。这确实给分裂合并操作增加了一点复杂度，但这是保证整个混合索引架构正确工作的必要步骤。

并发与性能

1、 你这个锁的粒度是多大的？是只有一个全局的锁来保护整个引擎，还是说你对数据结构做了更细粒度的锁定？

采用一个全局的读写锁来保护整个存储引擎。一次写操作（如 Put 或 Delete）需要同时修改哈希表和 B+树。如果采用细粒度锁（比如锁住单个 B+树节点），就需要设计一套非常复杂的锁协议来保证对两个数据结构修改的原子性，这会大大增加实现的难度和出错的风险。

2、 为什么选择读写锁，而不是更简单的互斥锁（Mutex）？在什么样的业务场景下，读写锁的优势才能最大化体现？

为了提升并发读取的性能。

互斥锁 (Mutex)：任何时候只允许一个线程进入临界区，无论这个线程是读还是写。如果一个线程在读，其他所有线程（包括读和写）都必须等待。

读写锁 (Shared Mutex)：它区分了“读操作”和“写操作”。规则是：

• 读锁共享：多个线程可以同时持有读锁，并发地进行读取，互不影响。
• 写锁独占：写锁是排他的。当一个线程持有写锁时，其他任何线程（无论读写）都不能获取锁。反之，当任何线程持有读锁时，写线程也必须等待。

3、在你当前的锁机制下，如果一个线程正在执行写操作（比如 Put），此时大量的读请求（Get）过来会怎么样？它们是都会被阻塞吗？

它们都会被阻塞。整个过程是这样的：

1. 写线程请求锁：一个执行 Put 操作的线程请求获取独占的写锁。
2. 获取写锁：

• 如果当前没有任何线程持有锁，该写线程会立即获得写锁。
• 如果当前有其他读线程正在读取，该写线程会等待，直到所有读线程都释放了读锁。

3. 写操作期间：一旦写线程成功获得了写锁，它就开始修改数据结构（哈希表和B+树）。在此期间，这个写锁是独占的。
4. 新请求到达：此时，无论来的是读请求（Get）还是新的写请求（Put），当它们尝试获取锁时（读请求尝试获取共享读锁，写请求尝试获取独占写锁），都会发现锁已经被一个写线程持有。因此，所有这些新来的请求都会进入等待队列，被阻塞。
5. 写操作完成：写线程完成操作后，释放写锁。然后，系统会根据具体的调度策略（通常是公平或读者优先/写者优先）唤醒等待队列中的线程。

复杂度

$O(1)$的平均单点查询复杂度，完全得益于我们引入的“哈希表”作为一级索引

平均单点查询复杂度为$O(1)$，如果只有B+树的话，$O(log N)$ 查询

流程是这样的：

1. 从 B+树的根节点开始。
2. 在当前节点中，通过比较 key 的大小，确定下一步应该访问哪个子节点。
3. 沿着路径一直向下访问，经过一层层的非叶子节点（索引节点）。
4. 最终到达包含该 key 的叶子节点。
5. 在叶子节点内进行查找，找到 key 对应的 value。

核心设计：哈希表里存的不是数据本身，而是指向 B+树叶子节点的“快捷指针”。

一次 Get(key) 的新流程如下：

1. 哈希计算 (O(1))：当 Get("some_key") 请求到达时，我们首先对 "some_key" 使用哈希函数，计算出一个哈希值。这是一个常数时间操作。
2. 定位桶 (O(1))：我们用这个哈希值对哈希表的数组大小取模，立即定位到哈希表中的一个特定位置（桶/bucket）。这也是一个常数时间操作。
3. 获取指针 (O(1))：在这个桶里，我们直接存储了一个指针。这个指针指向的，正是B+树中存储着 "some_key" 数据的那个叶子节点。
4. 直接访问 (O(1))：我们通过这个指针，“跳过”了从 B+树根节点开始的层层遍历，直接“瞬移”到目标叶子节点。
5. 节点内查找 (O(1))：B+树的节点大小是固定的（通常是几个KB），在节点内部进行小范围的查找（如二分查找），其时间开销可以视为常数。