C数据库设计，可以按多个字段排序

Question

如果对于我的特定应用程序（输入，查找和排序速度是优先级）而言内存不是问题，那么什么样的数据结构/场排名表？

例如，假设我想创建一个游戏名人堂，可以根据最高分数（与用户名无关），用户名（可以按同一用户的所有分数排在一起，然后按用户的最高分数排序） ，或达到的水平（独立于分数或名称）。在这个例子中，如果我按照每个玩家的最高分排序链接列表，矢量或任何其他连续的数据结构，它会搜索其他字段 - 比如级别和非最高分数 - 更迭代（即迭代所有人都在寻找舞台，或寻找特定的分数范围），除非我想出一些其他方式来存储输入新数据时排序的信息。

问题是在C/C++中是否有更高效（尽管是复杂的和内存消耗）的方法或数据库结构，可能为这种多字段排序启动。链接列表对于简单的分数排名似乎很好，我甚至可以通过对单个字段（玩家名称或达到的级别）进行散列来组织一个散列表，以便按单个字段进行排序，但其他字段则用O（N）来查找，更糟的是要排序。只有三个字段，我想知道是否有方法（如集合或二级列表），以防止事先知道的某些预先想要的类型迭代。

Answer 1

以与数据库相同的方式进行操作：使用索引结构。您可以将主要数据作为多个记录（结构），也许根据您的一个排序标准进行排序。然后你有索引结构，每个索引结构根据你的其他排序标准排序，但是这些索引结构不包含所有数据的副本，只是指向主要数据记录的指针。 （认为​​“索引”就像一本书中的索引，页码“指向”主要数据体）。

对索引结构使用有序链接列表将为您提供一种快速简单的方式来查看记录按顺序排列，但如果您需要搜索给定值，则速度会很慢，插入新数据时速度会相当慢。

哈希表将有快速搜索和插入，但（与正常的哈希表）将不会帮助你排序。

所以我建议某种树形结构。平衡二叉树（查找AVL树）在主内存中工作良好。

但不要忘记使用实际数据库的选项！像MySQL和SQLite这样的数据库管理器可以与您的程序连接，无需单独的服务器，并且可以使用嵌入到程序中的SQL，轻松地完成所有的排序和索引。它的执行速度可能比编写自己的主存数据结构要慢一些，或者如果使用库中的主存数据结构，但编码可能更容易，而且不需要编写单独的代码将数据保存在磁盘上。

Answer 2

所以，你已经知道如何存储你的数据，并保持它对单个字段的排序。假设单个条目的字段值是独立的，唯一能够获得所需内容的方法是保留三个不同的列表（使用您选择的数据结构），每个列表都按不同的顺序排序领域。你将使用三倍于单个列表的内存价值指针。

至于每个列表的数据结构应该是多少，使用binary max heap将是有效的。插入是lg（N），按顺序显示单个条目是O（1）（所以O（N）可以看到它们全部）。如果在这些列表副本中的某些条目需要按另一个字段进行分类排序，请考虑在比较函数调用中。