data-structures - 表的数据结构

Question

如果我有一个表，每行代表一条记录，并且有几列。我想对任何列进行快速查询和排序。我可以使用哪些数据结构？

我想节省空间。否则，我可以在每一列上缓存排序结果以进行查询和排序。但是除了表本身之外，如何消耗更少的空间呢？

Answer 1

根据数据的复杂性，您可能正在寻找关系代数的实现。也就是说，一组无序的元组。

通常实现是某种形式的B-tree。

Answer 2

这本质上是一个数据库编程问题。您将需要索引，每列一个（此答案的其余部分将假装我们在谈论单个索引；想象一下，如果需要，可以多次执行所有这些操作）。常见的解决方案包括哈希表和搜索树（例如 B 树），但当然，仅包含所有列条目的简单解决方案并不是特别节省空间。

答案是创建稀疏索引：将记录分组到块中，并仅存储索引中每个块中搜索键最低的记录。除非您遇到病态情况（始终添加非常低的值），否则这将在低空间要求下为您提供不错的性能。

为了处理病态情况，您可以考虑将记录分组到块中的不同方法，例如，保留一大堆尚未索引的记录，并且只将其中的一堆提交到一个组中（并将其编入索引）每当您可以找到一个在搜索键方面并非无处不在的子集时。

（这些只是想法。我更像是数据库的用户而不是数据库的程序员。尝试一些研究，看看比我了解更多的人在实践中做了什么。）