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