表的数据结构

Question

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

我想要节省空间。否则，我可以缓存每列的排序结果进行查询和排序。但如何消耗更少的空间，而不是桌子本身？

Answer 1

根据数据的复杂性，您可能正在寻找relational algebra的实现。那就是，unordered set of tuples。

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

Answer 2

这本质上是一个数据库编程问题。你需要索引，每列一列（这个答案的其余部分会假装我们正在谈论单个索引;想象一下，如果你需要的话，多做几次）。通常的解决方案包括散列表和搜索树（例如B-树），但当然一个简单的解决方案只包含所有的列条目，并不是特别节省空间。

对此的回答使得稀疏索引：将您的记录按块分组，并仅存储索引中每个块的搜索关键字最低的记录。除非你有病态（一直都会增加非常低的值），否则这将在低空间需求下给你体面的表现。

要处理病理情况，您可以查看以不同方式将记录分组为块，例如，通过保留一大堆尚未索引的至今的记录，并且只要将一大堆这样的记录提交到一个组中（并对其进行索引），只要您可以找到一个不在搜索关键字上的子集。

（这些只是想法。我更数据库比他们的程序员的用户，尝试了一些研究，看看有什么已经知道谁比我更要做人在实践中完成的。）