是否值得尝试编写万无一失的数据结构？
问题
我们需要以类似于表的方式存储数据，但是我们有非常严格的空间限制(每个10k+行表的~1MB)。我们存储这样的数据：
ID | reviews | factor | score | interval | etc.
---+---------+--------+-------+----------+-----
1 | 244 | 2.4 | 10 | 4268 | ...在一个简单的二进制格式(一个一维字节数组，其中每一行的索引可以简单地通过了解每一行的长度，这是固定的)。
只有一个函数读取此数据(按其索引获取一行)，只有一个函数追加一个新行(到末尾)。从表中移除项是永远不需要的(该表仅附加)。这两个功能都包含了相当数量的单元测试。
问题是:我们需要能够快速地遍历按不同列排序的行。换句话说，我们需要至少按两列对数据进行排序。
--一个简单的解决方案
为了解决这个问题，我们将实现同样是二进制数据块的索引。现在，我将通过创建只列出原始表中行的索引的有序数据结构来直观地做到这一点：
factor_index score_index
------------ -----------
6 2
2 1
3 6
1 4
. .将新行附加到表中的函数必须更新，才能使索引也被更新。
示例:要获得按得分排序的第一项，我们只需在索引表中查找score (2)的第一个值，并从原始表中获得相应的行(如果我们同意该表是零索引的，则为第三行)。
然而，有人建议我采取不同的办法。
--一个更复杂但更安全的
版本
我们不只是存储索引，而是在每个索引表中复制ID字段：
factor_index | ID score_index | ID
-------------+--- ------------+---
6 | 46 2 | 8
2 | 8 1 | 14
3 | 91 6 | 46
1 | 14 4 | 60
. | . . | .然后保持原始表按ID排序，并仅将索引用作原始表中二进制搜索的起始位置。
添加新记录的函数现在必须按ID执行二进制搜索，以查找插入新行的位置，并使索引更新。
为了获得按分数排序的第一项，我们在索引表中查找分数(2，8)的第一行，并使用索引(2)作为表中二进制搜索的起始位置。如果数据是有效的，我们甚至不需要进行二进制搜索，因为在位置2，我们将找到ID为8的行。但是，如果我们发现位置2的记录有不同的索引，我们继续进行二进制搜索以找到正确的数据，并记录错误。
这种方法的论点是，即使索引指向表中的错误行，它也会工作。
不过，我很难相信这种方法确实更好，原因如下：
- 它需要一个二进制搜索，这可能是一个新的bug来源。
- 它要求保持表的有序性，这意味着更复杂的插入(相对于简单的附加)。
- 它并不能防止主表出现故障:如果出现这种情况，索引甚至可能无法通过二进制搜索找到记录。
- 它需要编写(和测试)从未打算运行的代码。
- 它使用的数据比所需的要多。
问题
对于我们的应用程序来说，非常高的优先级是，上面的数据始终是有效的。但是，这是否有理由编写更复杂的数据结构和查找机制，以防止可能发生或不可能发生的边缘情况？难道不应该把时间和精力花在为更简单的版本编写更健壮的测试用例上吗？
回答 3
Software Engineering用户
发布于 2013-03-02 22:09:02
如果我正确地理解了您的索引，它们不是存储它们的最有效的方法。
无论如何，你不能同时在两把钥匙上整理你的桌子，所以我认为你根本不应该试着把它分类。相反，对索引进行排序。
10k行--一个两个字节的值可以指表中的任何条目。因此，构建最初以1..10k为种子的两个数组(或表中有多少个条目)。虽然这些不是CPU意义上的指针，但无论如何都要使用它们作为指针。根据表中的值对两个数组进行排序。
Insert是通过简单地追加记录，然后重建数组来处理的。是的，这是一项相当昂贵的操作，但是由于您已经指定了数组，所以数组并不大，不能增长太多，因此不应该经常这样做。你做的任何事都是天生的至少O(n)，一个完整的度假村只有O(n log n)，我会走后一条路。(你甚至可能会发现它更快，因为与移动记录相比，对主内存的写入要少得多。)
请注意，这些数组只是两个字节的值，而不是像您所指示的那样的键值对。
还有一些其他的事情也浮现在脑海中--你似乎异常关注数据的大小。这告诉我，要么您正在传输这些块(此时可以省略这些索引，因为它们可以在另一端重新创建)，要么您立即在内存中存储了大量这些数据。在后一种情况下，如果您使用的是支持弱引用的语言，则可以使用它们--让块的索引没有被积极地用于垃圾收集，然后在需要时重新创建。
Software Engineering用户
发布于 2013-03-02 20:03:47
如果数据有效性至关重要，那么对数据的任何转换都必须将数据从有效状态转换为有效状态。转换机制应确保给定有效输入的输出的有效性。不成功的转换应该安全地失败，使数据处于有效状态。
单元测试只能确保在编写测试时考虑的每个条件下转换都是有效的。在所有数据转换方法中建立一致性可以确保数据在所有可能的条件下都是有效的。
因此，如果数据有效性是一个高优先级，我建议您构建始终有效的数据修改方法，并对它们进行彻底的测试。不要相信一致性是巧合。
Software Engineering用户
发布于 2013-03-03 00:00:16
首先，有一件事可以反驳你的论点：
- 如果一个人想要像你写的那样使用ID，他肯定会首先实现一个ID到行索引(这样ID查找就不需要按特定的顺序查找原始表，并且您也不必在该表上实现二进制搜索)。
但是如果你想一想这一点，你就会发现现在你已经把原来的问题转移到了一个不同的层次--你必须确保ID到行索引没有不同步。当然，现在的优点是，当原始表的行顺序发生变化时，您可以独立地重建这个索引。这是有意义的，当你必须期待这样的变化，你知道它们何时发生，它们很少/在特定的时间点发生。
不过，这真的值得吗？当您100%确信原始表中的行号是有效且不可变的主键时，根据行号构建最简单的可能解决方案，其他一切都更容易出错和“过早无意义”。否则使用ID。
以下是一些无法确定行号是有效主键的方案：
- 关系数据库中的行通常不会有特殊的顺序。
- 在基于文件的场景中:数据量不断增长，由于空间限制，您必须将其拆分到多个物理表中。然后ID可能仍然是有效的主键，但行号不是。
在采用基于行号的方法时，请确保不处于这种情况。
https://softwareengineering.stackexchange.com/questions/189044
复制
腾讯云开发者
