缓存意识的B+tree是如何存储的？

Question

我是数据库新手，希望实现一个有缓存意识的B+tree。大量阅读建议将节点和叶子存储为连续内存。这是否假设在创建B+tree时，节点和叶子被存储在堆中，然后通过读写操作复制到磁盘中？有缓存意识的B+tree会告诉OS给它一组连续的物理页面吗？我认为答案是b/c应用程序不应该知道物理页是如何分配的，而连续内存仅指主内存页？

Answer 1

“缓存意识”位是指页面布局的一种特殊规则，它试图最大限度地利用CPU的第一级数据缓存，通常是针对特定的缓存行大小(例如64字节)进行优化。

一种标准技术(独立于高速缓存行大小)是在间接向量中使用偏移值编码，通常与“穷人的规范化密钥”(例如，通常从第一个字节开始的密钥的两个或四个字节，而不是与前辈共享)结合在一起。这减少了访问间接向量之外的数据的必要性--即保存在页面其他地方的堆中的实际密钥数据，而且很多查询(失败的查找)只能使用增强的间接向量中包含的数据来完成。这将最大限度地利用缓存，并将重击最小化。

其他方案将间接向量的元素形成一个迷你btree，其“页面大小”等于高速缓存线的大小。

还有一种方案将间接向量划分为大小为一个(或极少数)高速缓存线的子块，前缀截断(在一些论文中称为“前压缩”)仅在这些子块中使用，而不跨不同块使用。块“领导者”之间的二进制搜索用于识别目标块，然后以典型的前缀截断密钥序列的方式线性扫描目标块。

该方案的一个变体将块领导者存储在一个小型索引中，并将顺序子块保存在其他地方，以进一步提高缓存的利用率。不用说，页面内空间管理是一个绝对的噩梦。

许多其他的变化是可能的，但出版物似乎仅限于试图证明学术观点的学术论文，并且很少窥探重要数据库系统所使用的页面布局。

即使对于与前缀截断相关的键比较这样基本的内容，我可以在网上找到的唯一严肃的引用可以追溯到1990年：

DDJ 1990年12月-增压顺序搜索

对btree的CPU缓存问题有较好概述的论文：

• B树索引和CPU缓存 (Goetz Graefe和Per- and )
• 主存数据库的高速缓存索引结构 (Vilho )
• 使B+-树在主存中具有缓存能力 (君·劳和肯尼斯·罗斯)

对于底层存储的分页性质的意识--以及寻求、页读/写和批量读/写的不同特性--是一种不同的野兽，但也是重要的。它的结果往往令人惊讶，创新的设计。伯克利DB的Java版本就是一个例子，它只将日志文件保存到磁盘上，并在启动时从日志中重新构造内存中的btree。