database - DBMS 中使用的数据结构

Question

像 Oracle、MySQL 和 Sqlite 等 DBMS 中用于存储和检索记录的数据结构是什么？

Answer 1

通常是B 树的巧妙实现

从上面链接的维基百科文章：

m阶B树（每个节点的最大子节点数）是一棵满足以下属性的树：

1. 每个节点最多有 m 个子节点。
2. 每个节点（除了根节点和叶子节点）至少有 m⁄2 个子节点。
3. 如果根不是叶节点，则根至少有两个子节点。
4. 所有叶子都出现在同一级别，并携带信息。
5. 具有 k 个子节点的非叶节点包含 k–1 个键

其优点是可以在对数时间内访问数据，就像大多数搜索树（例如标准二叉树）一样，但在平均情况下时序属性更好。

Answer 2

MySQL具有可插拔的存储系统。这意味着引擎可以使用不同的存储。它目前有 5-6 个可供您使用。而且由于它是开源的，您可以看到它是如何完成的。

SQLite使用它自己的带有日志的 B-Tree 实现。开源——你可以看看。

Firebird和Interbase正在使用具有多记录版本控制系统的 B-Trees 进行存储。Firebird 是开源的。值得一看。

无法判断Oracle、MS SQL Server或其他专有数据库系统，因为它们对存储信息保密。