cache conscious B 树是如何存储的？
How is cache conscious B+tree stored?
我是数据库新手，希望实现一个具有缓存意识的 B 树。许多阅读建议将节点和叶子存储为连续内存。这是假设在创建B树时，节点和叶子都存储在堆中，然后通过读写操作复制到磁盘中吗？有缓存意识的 B 树是否告诉操作系统给它一组连续的物理页面？我认为答案是没有 b/c 应用程序不应该知道物理页面是如何分配的，而连续内存仅指主内存页面？
"缓存意识"位是指页面布局的一种特殊规则，它试图最大限度地利用 CPU 的第一级数据缓存，通常针对特定的缓存行大小(例如 64 字节)进行优化。
一种标准技术(与高速缓存行大小无关)是在间接向量中使用偏移值编码，通常与"穷人的规范化密钥"结合使用(例如，通常从第一个字节开始的两个或四个字节的密钥材料不与前任共享)。这减少了访问间接向量之外的数据的必要性 - 即保存在页面其他位置的堆中的实际关键数据，并且可以仅使用增强的数据中包含的数据来完成相当多的查询(失败的搜索)间接向量。这可以最大限度地提高缓存利用率并最大限度地减少抖动。
其他方案将间接向量的元素形成一个 mini-btree，其"页面大小"等于缓存行大小。
另一种方案将间接向量划分为一个(或很少)缓存行大小的子块，前缀截断(在某些论文中称为"前压缩")仅在这些子块内使用，而不是跨不同块使用.块"领导者"之间的二进制搜索用于识别目标块，然后以前缀截断键序列的典型方式对其进行线性扫描。
该方案的一种变体将块领导存储在一个迷你索引中，并将顺序子块保存在其他地方，以进一步提高缓存利用率。不用说，页内空间管理绝对是一场噩梦。
许多其他变体是可能的，但出版物似乎仅限于试图证明学术观点的学术论文，并且很少窥视重要数据库系统使用的页面布局。
即使对于与前缀截断相关的键比较这样基本的东西，我能在网络上找到的唯一严肃参考可以追溯到 1990 年：
DDJ 1990 年 12 月 - 增压顺序搜索
对 btree 的 CPU 缓存问题有很好的概述的论文：
- B-tree 索引和 CPU 缓存(Goetz Graefe 和 Per-?…ke Larson)
- 主内存数据库的缓存感知索引结构 (Vilho Raatikka)
- 使 B 树在主内存中缓存有意识(Jun Rao 和 Kenneth Ross)
对底层存储的分页性质的认识——以及寻道、页面读/写和批量读/写的不同特性——是一种不同的野兽，但也很重要。它通常会产生令人惊讶的创新设计。一个例子是 Berkeley DB 的 Java 版本，它只将其日志文件保存到磁盘，并在启动时从日志中重建内存中的 btree。