我应该如何在 Delphi 中实现一个巨大但简单的索引字符串列表？

关键词：

【中文标题】我应该如何在 Delphi 中实现一个巨大但简单的索引字符串列表？【英文标题】：How Should I Implement a Huge but Simple Indexed StringList in Delphi? 【发布时间】：2009-11-25 20:07:17 【问题描述】：

我使用的是 Delphi 2009。我有一个非常简单的数据结构，有 2 个字段：

一个字符串，它是我需要检索的关键字段，长度通常为 4 到 15 个字符。 作为数据字段的字符串，可以是任意大小，从 1 个字符到 10,000 个字符。

困难在于我可能有几百万条这样的记录，因此它们的总大小可能达到或超过 10 GB。显然，我正在寻找磁盘上的解决方案，而不是内存中的解决方案。

我的程序需要根据关键字段随机检索这些记录。这就是需要尽可能高效的部分。

我应该为这样一个简单的结构使用数据库吗？如果可以，哪个数据库最适合处理这个问题并且最容易实现？

或者，是否有一个简单的磁盘数据结构，不需要成熟的数据库也能正常工作？

---

好吧，我所需要的只是一个让我回到现实的答案。我一直在寻找比简单数据库更简单的东西。但是当没有答案是使用数据库时，我意识到我已经用我自己对另一个问题的答案回答了这个问题：Best database for small applications and tools。

我的回答是DISQLite3 对应the reasons I specified there。这就是我可能会使用的实现方式。

---

一些更好的答案和一些可能性。那太棒了。我将能够尝试几种不同的方法，看看哪种方法最有效。

---

更多的思考，我不得不将接受的答案更改为 GpStructuredStorage 解决方案。

在我的例子中，一百万条记录总计几千兆字节会给数据库结构带来压力。具体来说，大多数数据库中用于存储索引的 B* 树速度很快，但对于某些操作（例如重新索引一百万个值）会变慢。

唯一比 B* 更快的索引是哈希表。这正是 gabr 建议的 GpStructuredStorage 解决方案中提供的内容。我认为他将哈希值分段以提供 4 级目录结构的方式非常优雅。

我可以使用哈希解决方案的关键原因是我只需要通过密钥进行随机访问。我不需要按键排序。如果需要排序，那么哈希表的速度优势就会丧失，数据库系统将是无脑赢家。

当我着手实现这一点时，我应该将该技术与数据库进行比较。也许我会与 Firebird 和 SQLite 进行比较，它们都是值得的对手。

---

还有一个后续：

我刚刚通过A. Bouchez 发现了Synopse Big Table，它专为提高速度而设计，几乎完全符合我的问题的规格。我会在几个月后进行实施时先尝试一下，然后在这里报告我的结果。

---

很久以后的后续行动（2015 年 7 月）

我从未尝试过 Synopse Big Table。到目前为止，我一直坚持使用我的 B* 树。但现在我已经升级到 Delphi XE8 并计划使用 FireDAC 和 SQLite 的数据库解决方案。

【问题讨论】：

您是否只需要对数据进行只读访问？或者你会随机添加记录吗？ 我还需要修改、添加和删除记录。修改可能意味着改变记录的数据长度。 【参考方案1】：

对于超过 10GB 的数据，数据库正是您所需要的。它将处理快速定位数据的索引（您的随机检索）、添加、修改和删除数据的功能以及实际存储，如果您愿意，还可以处理更多。

这里有几十篇文章涉及哪些数据库可在 Delphi 中使用，包括内置和 FOS 数据库，如 Firebird。

【讨论】：

那么哪个数据库最适合这种特定的数据结构，或者你说这无关紧要？ 没关系。有几种可行的选择； Firebird 是我自己用过的一款，效果非常好，而且可以免费启动。 :-) 根据您的特定需求（完全包含在可执行文件中，或者不需要 DBA 等），还有其他可能会更好地工作；如果没有关于您实际在做什么的更多信息，我无法推荐任何更具体的内容。 为单个两列携带整个数据库似乎是一种耻辱。因此，我会选择满足您的性能要求的最小、最简单、功能最少的数据库。特别是，您似乎不需要 SQL 或关系，因此支持这些功能对您没有任何价值。如果 Delphi 绑定可用，BDB（如下）将是一个不错的选择。 @Larry：我不得不不同意。 :-) 需要快速随机访问的 10GB 数据不仅仅是一个简单的两列数据库。当然，您对“快速”的定义可能与我的不同。考虑到现在桌面的标准（注意斜体）RAM 是 3 或 4 GB，10GB 相当大。关键是“快速”部分，它迫切需要具有良好索引能力的优化数据库。 Zeos 是访问多个数据库的好库，只要您不使用 D2009 或更高版本；他们还没有非 beta Unicode 版本可用。 @Larry：对不需要的功能的支持不会带走任何东西。然而，在编写“简单”磁盘数据结构时，一个成熟的数据库系统可能已经在文件访问和缓存策略上投入了更多的工作，而不是他们自己可以合理地完成的工作。为什么不利用它？【参考方案2】：

为什么要吹牛？只需使用GpStructuredStorage（4 TB 限制，并且几乎没有时间投入到课堂上，你可以过去），你需要几个小时才能习惯它，但值得花时间。 希望对你有帮助

GpStructuredStorage 可以非常快地检索文件名（我已经测试过），您需要将每条记录保存为 GpStructuredStorage 中的文件，并将每个名称作为字符串检索到字符串列表中，100 万个字符串名称（因为您提到关于stringlist）需要几MB的RAM，并不多，使用TStream后代将数据写入GpStructuredStorage中的文件，我今天没有时间写一个简单的例子，但是周六或周日我会写一个教程GPStructuredStorage 在我的博客上。

---

_{[由 gabr 添加 - 我希望这不会被视为严重违反网络礼仪。只是我的想法不适合评论（按大小计），并且添加另一个答案只是为了写这个感觉很愚蠢...]}

虽然 GpStructuredStorage 可以存储大量数据，发现它可能是一个缓慢的过程。在这种情况下，我通常做的是创建密钥的哈希并将其转换为十六进制（例如 00FFA784）。然后我将此十六进制哈希转换为文件夹结构（在本例中为 /00/FF/A7/84）并将相关数据存储在此文件夹中，作为文件、属性或两者的组合。

这种方法可以加快数据检索速度，但会减慢数据插入速度，因此建议仅用于大多数静态数据。如果数据是相当动态的，我当然建议使用数据库而不是 GpStructuredStorage。

【讨论】：

我听说过 GPStructuredStorage，但不知道它可能适用于这个问题。也许是的。唯一的问题是，一旦它有一百万个项目，它会变得像 Windows 文件系统一样慢，还是 gabr 使用快速树或他的大缓存优化了检索？当我比较时，我可能会尝试这个。价格合适。 实际上，我不知道 GpStructuredStorage 在这么大的集合上会如何表现，但当然欢迎您尝试 :) 事实证明，数据库将在第一次全部创建（从另一个数据集导入）。之后，它将逐个记录地更新（一次只有几条记录），所以也许在我的情况下，根据 gabr 的建议，使用您的哈希函数作为文件夹路径，GpStructuredStorage 可能是一个可能的解决方案。 我特别喜欢 gabr 将哈希分组为 2 个字符组合以形成 4 级文件夹结构的想法。有一百万条记录，每个级别平均只有 33 个条目，这应该可以相当快地找到文件，即使只是使用顺序目录/文件搜索。 gabr：在***.com/questions/222699/… 中，您回答了 Firebird，我表示同意您的看法。但是我还没有尝试过Firebird。对于我的特定问题，您如何将它与 GPStructuredStorage 解决方案进行比较？【参考方案3】：

您应该分析您的数据。如果

相当大一部分数据值大于默认文件系统块大小， 您不想使用 SQL 在数据值中进行搜索（因此它们存储的格式无关紧要），并且 您确实需要对整个数据库进行随机访问，

那么您应该测试压缩数据值是否会提高性能。数据值的解压缩（尤其是在具有多核的现代机器上，在后台线程中执行）应该只会对性能造成很小的影响，但是从硬盘读取更少的块（特别是如果它们不在缓存中）会带来收益) 可能更大。

但你需要衡量，也许数据库引擎无论如何都会存储压缩数据。

【讨论】：

这是个好主意。压缩可能会加快。我会先实现，看看它是否足够快。如果没有，我会试试你的建议。【参考方案4】：

BerkleyDB 就是这样

【讨论】：

它有 Delphi 绑定吗？一个快速的谷歌并没有显示太多。 @Glex：一位开发人员，没有下载可用，SVN 包含 2 个修订版，最后一个将近 3 年。看起来没有那么有希望。 这些只是绑定老兄。如果 BerkleyDB 在过去 3 年中发生了如此大的变化，那么无论如何修复 API 更改都不会那么难。 也许 BerkleyDB 没有太大变化，但我怀疑这些文件在 Delphi 2009 或 2010 中没有任何变化也能正常工作。你试过了吗？ 问题部分中有一篇文章介绍了如何更改以使其在 Delphi 7 中工作。Delphi >7 是 Delphi 7 的严格子集。但是，好点，我还没有尝试过。 【参考方案5】：

由于您的数据超过 3GB，因此您需要确保您选择的任何数据库引擎都可以处理这么大的表，或者将数据拆分为多个表，我建议您不管数据的最大大小是多少都这样做单表。如果您执行拆分，请在逻辑键中断处尽可能均匀地执行它，以便通过键的前两个字符轻松确定要使用哪个表。这将通过消除任何与您的查询开始时永远不匹配的记录来大大减少搜索时间。

如果您只想要原始性能，并且只对数据执行只读查找，那么您最好使用有序索引文件来提供服务，该文件使用固定大小的键记录指向您的数据文件。然后，您可以轻松地对此数据执行binary search 并避免任何数据库开销。为了进一步提高性能，您可以将中点预加载/缓存到内存中以减少重复读取。

您的规格的简单固定大小记录可能如下所示：

type
  rIndexRec = record
    KeyStr  : String[15];  // short string 15 chars max
    DataLoc : integer;     // switch to int64 if your using gpHugeFile
  end;

对于初始加载，请使用 SysTools 中的 Turbo Power 排序，可以在 songbeamers 网站上下载 Delphi 2009/2010 的最新版本。 DataLoc 将是您的数据字符串记录的流位置，其写入/读取可能如下所示：

function WriteDataString(aDataString:String;aStream:tStream):integer;
var
  aLen : integer;
begin
  Result := aStream.Position;
  aLen := Length(aDataString);
  aStream.Write(aLen,sizeOf(aLen));
  aStream.Write(aDataString[1],aLen*sizeOf(Char));
end;

function ReadDataString(aPos:Integer;aStream:tStream):String;
var
  aLen : integer;
begin
  if aStream.Position <> aPos then
    aStream.Seek(aPos,soFromBeginning);
  result := '';
  aStream.Read(aLen,SizeOf(aLen));
  SetLength(Result,aLen);
  if aStream.Read(Result[1],aLen*sizeOf(Char)) <> aLen*SizeOf(Char) then
    raise Exception.Create('Unable to read entire data string');
end;

当您创建索引记录时，dataloc 将设置为数据字符串记录位置。加载记录的顺序无关紧要，只要对索引记录进行排序即可。我只是使用这种技术来保持 60 亿条记录数据库的最新状态，每月更新一次，因此它可以轻松扩展至极致。

编辑： 是的，上面的代码限制为每个数据文件大约 2GB，但您可以使用 gpHugeFile 或分段来扩展它。我更喜欢分割成多个

【讨论】：

在 64 位 Delphi 可用之前，您的代码被限制为 2GB 文件。 可能。它需要时间测试来查看它的速度，并与已经开发的数据库进行比较来验证。【参考方案6】：

如果您更经常需要大型数据集，并且有一些闲钱，只需将 16GB（500-750 欧元）塞入一台机器，然后使用您查询的一些 64 位编译器 (*) 创建一个单独的进程在例如共享内存或其他 IPC 方法。

在这种情况下，您可以使用内存中的方法，直到 Delphi 64 位最终问世。由于您的数据看起来很简单（从 char 数组到 char 数组的映射），因此很容易通过 IPC 导出。

当然，如果这种方法对您的情况有任何好处（比如它是缓存左右），我无法从您的问题中确定。

(*) 我当然推荐 FPC :-)

我这样做了一次，直到大约 500 万个对象，5 GB 的数据。

我获得了开源我为它制作的容器类型的许可，它们位于：

http://www.stack.nl/~marcov/lightcontainers.zip（警告：非常脏的代码）

mghie：用另一个陈词滥调来回答：没有灵丹妙药

数据库也有很多其他假设

他们的通用方法使内存的使用效率相对较低。最值得注意的是，您使用普通内存存储技术的数据集在可承受的内存范围内，当然对于服务器（我在这里的错误假设，显然）通常比对于客户端更大。 数据库假设它们的结果集可以通过相对直接的处理方式在数据库服务器中缩减为小型集，并通过索引进行辅助。 它们的延迟相对较高。 它们在某些类型的处理中相对较差（如多维分析/OLAP，这就是为什么需要为此扩展数据库的原因）

这使得数据库相对不适合用于例如缓存，负载均衡器等。当然，前提是您需要速度。但最初的问题对我来说有点速度敏感。

在过去的工作中，我在一家面向数据库的公司的职责是做所有事情，但 IOW 在标准方法无法破解它时解决问题（或者需要 4 个插槽 Oracle 服务器来完成预算不保证的工作）此类费用）。上面写的解决方案/hack 有点 OLAPpy，并且连接到硬件（一个 rfid 芯片编程设备），需要一些有保证的响应时间。两个月的编程时间，还在运行，连windows server + oracle的license都买不起。

【讨论】：

这种方法的问题是所有数据都需要在应用程序启动时读入内存，或者至少索引结构需要。索引结构也需要首先计算和编写。在开发这一切时，开始重复已经为数据库系统完成的大部分工作...... 是的，mghie 确定了主要问题。此外，为我的所有用户的机器购买 16 GB 的 RAM 对我来说是非常昂贵的。 :-) lkessler：如果是针对用户应用程序，那就算了。 mghie：我需要更多的空间来评论你，我会在帖子中这样做。 @Marco：感谢您的编辑，我现在了解您的来源并同意大多数观点。但是在您关于数据库假设的 4 点中，至少第二点与这个问题完全匹配，第四点在这里无关紧要。其他两个是真正值得关注的问题，但是虽然我认为经过调整的手写解决方案可以轻松胜过许多数据库，但在这个问题的背景下，开发工作是否会得到充分利用是值得怀疑的。毕竟它可能只是整个应用程序的一部分。应该只在在清楚（测量！）这是瓶颈之后再努力。 在这种情况下，我猜不是（尽管我不得不倒回我最初回答的原始问题）。当我回复它时，我在深夜破解了 synedit，我很沮丧。我想你知道这种感觉:-)【参考方案7】：

Synopse Big TableA. Bouchez。请参阅his answer to my other question 关于 SQLite/DISQLite。

当我第一次问这个问题时，它甚至还没有开发出来，但现在它已经是一个相当成熟且功能齐全的单元了。

【讨论】：

如何在 C++ 中实现强大的数据持久层？

...式来连接到我的MySql数据库。我有这些问题：-我无法决定应该使用哪种模式，DAO，存储库、工作单元、工厂..-我在C++中找不到一个很好的数据访问模式示例，我知 查看详情

如何在 C# 中实现交互式决策树

...路径，以便进入下一组选项，直到他们到达一个结局，即应该实现这样的目标：我尝试了以下代码，但每次只评估左侧。我想知道如何才能获得像上图这样的结果（覆盖所有分支）？例如，如果用户选择 查看详情

如何在 Vue 应用程序（使用 Vuetify.js）中实现带有验证的简单表单？

...加一个简单验证的联系表单。我是新手，所以我不确定它应该如何在Vue组件中实现。我想实现 查看详情

在 Delphi 中实现 OAuth 提供程序

】在Delphi中实现OAuth提供程序【英文标题】：ImplementingOAuthProviderinDelphi【发布时间】：2011-01-2316:40:12【问题描述】：我已经开发了一个RESTWeb服务，并且我想实现一个OAuth服务提供者来验证主要是两条腿的OAuth请求。谁能指出我在De... 查看详情

如何在自定义 delphi 组件中实现 stringlist 属性？

】如何在自定义delphi组件中实现stringlist属性？【英文标题】：Howtoimplimentastringlistpropertyinacustomdelphicomponent?【发布时间】：2011-05-0207:46:11【问题描述】：我正在创建我的第一个自定义Delphi组件。它基本上是一个自定义的Tpanel，上... 查看详情

如何在阻塞模式 NIO 中实现超时？

】如何在阻塞模式NIO中实现超时？【英文标题】：HowdoesoneimplementatimeoutinblockingmodeNIO?【发布时间】：2013-02-1317:58:10【问题描述】：我没有使用任何选择器或类似的东西。我只有一个简单的ServerSocketChannel监听和一个SocketChannel以阻... 查看详情

如何在 GUI 编辑器中实现文档的版本跟踪

...处理它。它看起来像是一个用于文档的git？作为用户，我应该 查看详情

如何在 C# 中实现 glob

...会觉得有用。【问题讨论】：经过一些google-ling我发现glob应该做什么。en.wikipedia.org/wiki/Glob_(program 查看详情

你如何在方案中实现一个简单的列表迭代器？

】你如何在方案中实现一个简单的列表迭代器？【英文标题】：Howdoyouimplementasimplelistiteratorinscheme?【发布时间】：2021-12-0112:04:49【问题描述】：我正在尝试仅使用基本函数（car、cdr、cons等）比较Scheme中列表列表中的条目，但不... 查看详情

如何在 SQL 中实现聚合？ （这与 GroupBy 无关）

...：2018-06-2903:51:22【问题描述】：在大学项目的范围内，我应该实现我的数据库的聚合。我得到了一个类似于这个的实体关系模型：现在我应该实现一个创建这样的数据库的SQL脚本，但是我在谷歌或其他任何地方都找不到关于这个... 查看详情

delphi如何在delphi中实现托盘图标

参考技术A在c++builder的Sample组件页下有一个TrackIcon控件，可以实现托盘图标。可以Delphi没有对应的控件。 查看详情

如何在 iOS 11 中实现音量快门？

...的相机应用中实现音量快门。当用户按下音量按钮时，我应该得到一个拍照的事件。我正在寻找满足以下要求的实现：即使当前音量处于最大，并且用户按下音量调高按钮，它也应该可以工作。屏幕上的UI不应显示音量已更改。... 查看详情

如何在 UITableView 的索引列表中实现放大镜？ [关闭]

...想在Swift中的UITableView的索引列表中实现一个放大镜。它应该是这样的：有没有简单的方法来实现它？放大镜应该是一个按钮。通过按下这个按钮类似于tabl 查看详情

我应该如何在语法 AI 中实现人类思维逻辑？

】我应该如何在语法AI中实现人类思维逻辑？【英文标题】：HowshouldiimplementhumanthinkinglogicingrammarAI?【发布时间】：2019-10-3100:01:05【问题描述】：正如您在标题中看到的那样，我正在寻找一种有用的方法来将人类思维逻辑实现到语... 查看详情

如何在 HTML5 中实现一个简单的音频播放列表

】如何在HTML5中实现一个简单的音频播放列表【英文标题】：HowdoIimplementasimpleaudioplaylistinHTML5【发布时间】：2011-03-3002:05:12【问题描述】：我有一个mp3格式和ogg格式的文件列表（每种格式都有两种格式）。我想要一个播放列表，... 查看详情

尝试在 Reactjs 中实现一个简单的承诺

...我有一个基本的承诺（从别人的代码中提取），但不知道如何使它变得有用。到目前为止我所拥有的（在我的render()函数中）varpromise=newPromise((resolve,reject) 查看详情

如何在我的游戏中实现脚本？

...数字时不必重新编译所有内容。我的问题是我不知道脚本应该如何与游戏交互。我使用的脚本语言是angelscript。现在，我有一个状态：介绍状态，我用它来测试我的游戏“引擎”中的大多数模块（它更像是一个松散的 查看详情

java示例代码_我应该如何在Java中实现字符串到方法的映射

java示例代码_我应该如何在Java中实现字符串到方法的映射 查看详情