表的數據結構

Question

如果我有一個表，每行代表一個記錄，並有幾列。我想對任何列進行快速查詢和排序。我可以使用哪些數據結構？

我想要節省空間。否則，我可以緩存每列的排序結果進行查詢和排序。但如何消耗更少的空間，而不是桌子本身？

Answer 1

根據數據的複雜性，您可能正在尋找relational algebra的實現。那就是，unordered set of tuples。

通常的實現方式是B-tree的某種形式。

Answer 2

這本質上是一個數據庫編程問題。你需要索引，每列一列（這個答案的其餘部分會假裝我們正在談論單個索引;想象一下，如果你需要的話，多做幾次）。通常的解決方案包括散列表和搜索樹（例如B-樹），但當然一個簡單的解決方案只包含所有的列條目，並不是特別節省空間。

對此的回答使得稀疏索引：將您的記錄按塊分組，並僅存儲索引中每個塊的搜索關鍵字最低的記錄。除非你有病態（一直都會增加非常低的值），否則這將在低空間需求下給你體面的表現。

要處理病理情況，您可以查看以不同方式將記錄分組爲塊，例如，通過保留一大堆尚未索引的至今的記錄，並且只要將一大堆這樣的記錄提交到一個組中（並對其進行索引），只要您可以找到一個不在搜索關鍵字上的子集。

（這些只是想法。我更數據庫比他們的程序員的用戶，嘗試了一些研究，看看有什麼已經知道誰比我更要做人在實踐中完成的。）