data-structures - 大于内存的数据结构及其通常的处理方式

Question

假设我有一个基于文件的数据结构，例如 B+ 树。我的理解是数据应该存储在磁盘上，但索引通常加载在内存中。如果你有一个很大的文件，连它的索引都装不进内存怎么办？通常如何处理？其次，由于索引是一棵树，而不是线性数据集，它在磁盘上通常是如何布局的？

我基本上很好奇它在现实世界的项目(例如 Berkeley DB)中是如何完成的。显然我对大笔画感兴趣。我希望得到一个想法，这样当我深入研究我的数据库书籍的 B-Tree 部分时我就有了一些上下文(或者从多年前的 CS XYZ 中慢慢记忆)

Answer 1

B 树适用于基于页面的系统，其中给定节点适合页面。要在 B 树中查找条目，一次只需要加载一页，因此您可以这样做。

即使更新它们也不需要同时在内存中存储大量页面 - 我想最困难的操作是在重组节点时删除，但如果仔细实现，甚至可以相对完成内存中的几页。