假设有一个文件包含未排序的学生信息列表，其中包括学生 ID 号以及其他信息。
我想制作一个根据学生证号检索学生信息的程序。为了提高效率，我将学生 ID 存储在 B 树中。
因此，当我输入学生 ID 号时，它会搜索 B 树以查看其是否存在。它还做了一件事。如果它找到学生 ID 号，那么它还会返回该学生信息在文件中的位置。这是辅助键。该程序使用这些信息来定位学生的其余信息并将其打印到屏幕上。
这可以做到吗？这是b树的工作原理吗？
问问题
857 次
3 回答
1
B 树的工作原理是根据键存储值，并允许您在对数时间内找到给定的键及其关联值。所以第二件事不称为辅助键，它只是值。在这种情况下，它是文件的偏移量，这使得它本质上是一个指向值的指针。
这是使用 B 树的一种非常合理且非常常见的方式。
于 2010-05-08T08:27:03.687 回答
1
您所描述的与B-trees无关（顺便说一句，您确定您了解B-tree是什么吗？很多人将它们与二叉树混淆），并且文件位置不是“辅助键”，而是学生 ID 映射到的值。
但是，关系数据库内部的工作方式确实与您所描述的非常相似 - 数据库记录存储在任何有可用空间的地方，并且索引将索引列中的值映射到记录的位置。
于 2010-05-08T08:30:43.540 回答
0
B-Tree是一个索引。使用B-tree，您可以使用索引非常有效地找到值。索引本身有节点和叶子。每个节点都有以组织树的内容。节点指针指向其他节点或叶子。所以节点持有一些值和一些指针。节点指针是指向索引文件的偏移量。叶子也包含值和指针。不同之处在于叶子中的指针是数据文件的偏移量并指向真实文件。
因此，当您搜索一个值时，您正在使用索引来返回存储真实记录的文件偏移量。例如，您正在查找 ID=1 的记录，您将获得偏移量 10240，然后您如果您有 1KB 块，则打开数据文件以读取块 10。然后从这个偏移量您可以访问记录中的所有数据，例如用户名！
另一种实现是使用 BTrees，其中叶子不指向其他文件，但它们只包含第二个列。例如，如果您需要使用 id 查找用户名，您可以拥有一个 B 树，其中叶子具有以下结构：第一个值是 id，第二个是用户名，因此您可以从索引中获取用户名。
您也可以使用 B+ 树。B+ 树的实现类似于 B 树，但它们将叶子保存在列表中。因此您可以将索引用于 >、< 等运算符。
于 2011-09-02T21:36:34.313 回答