ale*_*cco 3 algorithm database-design external-sorting
假设您在磁盘上有一个包含 n 个对象的大型集合，每个对象都有一个可变大小的字符串。使用纯字符串比较为这些对象建立索引的有效方法的常见做法是什么。由于大小和 I/O 的原因，将整个字符串存储在索引上从长远来看是令人望而却步的，但由于磁盘具有高延迟，仅存储引用也不是一个好主意。
我一直在考虑使用类似 B 树的设计并尝试使用这种方法，但找不到任何数据库实现。事实上，很难找到主要数据库如何实现字符串索引（它可能会迷失在 SQL 级信息的大量结果中。）
蒂亚！
编辑：将标题从“有效外部排序和搜索具有大字符串的存储对象”更改为“有效存储字符串的外部索引”。
“前缀 B 树”或“简单前缀 B 树”在这里可能会有所帮助。
“简单前缀 B 树”稍微简单一点，只存储分隔两个项目的最短前缀，而不尝试消除这些前缀中的冗余（例如，对于“天文学”和“方位角”，它只会存储“as”和'az'，但不要试图避免重复 'a')。
“前缀 B 树”与您所描述的接近 - 类似于特里树，但在 B 树结构中，当主要存储在磁盘上时，可以提供良好的特性。尽管如此，它的目的是删除（大部分）构成索引的前缀中的冗余。
还有一个问题：你真的需要按顺序遍历记录，还是只需要快速查找指定的记录？如果后者足够，您也许可以使用可扩展散列代替。可扩展散列已经存在（以多种不同的形式）几十年，并且仍然运行良好。总体思路相当简单：将字符串散列以创建固定长度的键，然后创建这些固定长度伪键的某种树。与（几乎）任何散列一样，您必须准备好处理冲突。与其他哈希表一样，散列和冲突解决的细节各不相同（尽管可扩展散列可能不如内存中散列那么多）。
至于实际使用，主要的 DBMS 和类似 DBMS 的系统都使用上述所有内容。B 树变体可能是通用 DBMS 市场中最常见的（例如 Oracle 或 MS SQL Server）。可扩展散列用于大量更专业的产品（例如，Lotus Domino Server）。