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