B树如何在磁盘上存储？

Question

我知道如何在内存中实现B树，但不清楚如何将B树存储在磁盘上。我认为有两个主要的区别:

1. 内存指针和磁盘地址之间的转换，请参见此帖子。
2. 如何在插入新的k/v项时拆分页面？在内存中很容易实现。

谢谢。

- Chang

---

可能是重复的问题https://dev59.com/r0fRa4cB1Zd3GeqP-pwN，尽管那里的答案并不是很好。 - Manuel Salvadores

你最后解决了吗？这里有一个不错的开源实现：https://github.com/jankotek/JDBM3，但需要一些时间来阅读。作为开始，您可以查看：https://github.com/jankotek/JDBM3/blob/master/src/test/java/org/apache/jdbm/BTreeTest.java。如果您找到更好的资源，请分享出来。 - Sohaib

Answer 1

这完全取决于您使用的数据库管理系统。如果想知道在MS SQL Server中如何实现，需要了解以下内容：

• 页（我猜几乎所有现代DBMS都有）- 在SQL Server中它们是8KB。数据库文件由页面组成。
• Extents - 8个连续页面的逻辑组。
• （S）GAM - （共享）全局分配图。包含有关空闲和占用的extents的信息的位图。这是数据库文件上最早的页面之一。
• IAM - 索引分配映射。您可以找出哪个索引/堆存储在哪个extent中。有了这个信息，您可以获得存储索引/堆的文件中的位置。

使用IAM和GAM（或SGAM），您可以拆分页面-只需将页面的一部分（应该溢出的部分）移动到文件上的另一个页面即可。

IAM和GAM也是您第一个问题的答案。

这些名称大多来自于MS SQL Server，但我非常确定，在其他DBMS中，解决方法相当相似。

希望能对您有所帮助。

- Marcin Krupowicz

Answer 2

我的建议是看一下书籍数据库系统实现。

第2章“数据存储”和第3章“表示数据元素”将为您提供有关此问题的一些提示。

第4章索引结构中有一节关于B树的内容。

这是我迄今为止在这个主题上找到的最好的信息来源。

- Manuel Salvadores

---

这个主题有很多书籍，例如《数据库系统概念》(http://codex.cs.yale.edu/avi/db-book/)的第11章。然而，它们都没有讨论实际实现。 - Chang