使用 SQLite 数据库的简单文本索引器

• 下载源文件 - 481.23 KB

引言

使用 SQLite 的文本索引器

SQLite 是一个强大、免费、开源的数据库。它实现了出色的 B 树，速度快且体积小。SQLite 不受版权限制，因此您可以在任何商业项目中使用它。本项目广泛使用 SQLite 的 B 树来索引文本文件。每个文本文档都会被扫描，内容会被分词以在 SQLite 数据库中构建一个字典。后续搜索将针对字典和相关的映射表进行，以检索包含搜索字符串的文件名。

本文假定读者精通 C++ 和数据结构。此外，对 Windows API 的深入理解也是必要的。

为什么使用 B 树？

一个平衡良好的 B 树比哈希表具有几个优势

1. 插入新项更快。
2. 搜索“最接近匹配”项又快又容易。这在构建搜索字典时非常重要。搜索可以使用部分 string 进行，例如，要搜索单词 'where'，我们可以从 string 'whe' 开始。

一旦获得了第一个“最接近匹配”节点，就可以轻松地遍历 B 树列表以获取匹配的节点。

设计

索引器由一组 B 树（单词词典和 MAP 表）以及一系列“观察者”组成，这些观察者监视“用户输入”、“文件更改”和“系统空闲时间”，以更新或查询 B 树。每个观察者都在单独的线程中运行。

1. “用户输入”观察者读取用户的输入并查询索引器以获取匹配项
2. “文件更改”观察者等待观察目录的文件更改通知，并将更改信息排队到一个列表中。
3. “系统空闲时间”观察者在系统空闲时唤醒，并处理排队的文件更改信息。该观察者负责索引已修改的文件。

文件更改观察者

此观察者打开“settings.ini”文件（位于“INDEXER.EXE”所在的文件夹中）中指定的目录名。然后，它创建一个 IoCompletionPort 并等待文件更改。“IoCompletionPort”允许单个线程同时观察多个目录。它使用“ReadDirectoryChangesW” API 在 IoCompletionPort 报告完成状态时从系统检索文件更改。所有新建、修改或删除的文件名都会被放入文件名列表中。

类名：CFileObserver （filechg.h 和 filechg.cpp）

系统空闲观察者

此观察者大部分时间处于睡眠状态，一旦唤醒，它将使用 NTDLL.LL 提供的“NtQuerySystemInformation” API 来计算 CPU 使用率。如果 CPU 使用率低于 5%，并且文件名列表中（由文件更改观察者排队）有文件名，它将出队文件名，解析并索引文件内容。

类名：CIdleObserver （observer.h 和 observer.cpp）

用户输入观察者

此观察者在‘STDIN’上等待用户输入，并查询索引器以检索包含输入字符串的文件名。它在主应用程序线程中运行，并将一直运行直到用户按下 CTRL+C。

类名：CInputObserver （observer.h 和 observer.cpp）

索引器

此类用于索引文件内容。它使用字典查找算法来索引和搜索单词。提供的示例代码中只有一个字典。如果您需要高性能查找，您应该根据单词一部分（例如，单词的前三个字符）的哈希值创建字典数组。在这种情况下，字典将是 B 树的哈希表，应该提供快速查找。有关索引器的架构设计，请参见下文。

1. Dictionary （CIndexer 类的 m_dict ）

   此表将单词映射到其地址。地址是一个 64 位整数。每个查询都将从该表中查找单词的地址，然后使用该地址进行所有其他表查找。

   Word1	Address1
   Word2	Address2
   Word3	Address3

2. 文件映射表（CIndexer 类的 m_file ）

   此表将文件名映射到 FILE ID。每个 FILE ID 是一个唯一的 64 位整数。

   File name1	FILE ID1
   File nam2	FILE ID2
   File name3	FILE ID3

3. 文件 ID 到文件名映射表（CIndexer 类的 m_fileId ）

   这是通过 FILE ID查找文件名的反向查找表。

   FILE ID1	File name1
   FILE ID2	File name2
   FILE ID3	File name3

4. 字地址到文件 ID 映射表（MAP 表）（CIndexer 类的 m_map ）

   此表将单词地址映射到一组 FILE ID。每个单词地址条目都是一个向量记录的主键，该向量包含至少包含该单词一个出现的文件 ID。

   Address1	FILE ID1, FILE ID2
   Address2	FILE ID1
   Address3	FILE ID3

索引算法

• 如果文件名是新的，则在 FILE ID 表中创建一个条目。同时，在反向查找表中也创建一个条目。
• 通过逐行读取并对字符串进行分词来解析文件内容。每个 token 被假定为一个 WORD，并索引该单词。
• 在字典中查找以获取单词的地址。如果单词不在字典中，则创建一个条目。
• 使用单词地址作为主键查找 MAP 表以检索 FILE ID 向量。将新的 FILE ID 插入向量并将其保存在数据库中。
• 在行号映射表中创建行号和列号条目。

搜索算法

• 从字典中获取最接近匹配的单词地址（例如，搜索“w”可能会得到“where”、“while”、“which”等）。
• 对于每个单词地址，查找 MAP 表以检索 FILE ID。
• 对于每个 FILE ID，查找文件 ID 到文件名反向查找表以检索文件名。
• 查找行号映射表以获取单词在文件中的行号和列号。

源代码

源代码组织如下。

目录‘./sqlite’包含所有 SQLite 源代码。我仅从 SQLite 源树中挑选了相关的‘C’和‘H’文件，并修改了一些文件以移除额外的依赖。如果您想使用 SQLite 网站（http://www.sqlite.org）上的最新代码，您将需要修改代码使其能够工作。

• 目录‘./indexer’包含所有索引器代码
• 所有项目文件都基于 Visual Studio 2005
• 二进制文件创建在 ./bin/win32 目录中
• 设置文件（settins.ini）位于 ./bin/win32 目录中
• 索引文件创建在 %TEMP%/index 目录中

历史

• 2006 年 6 月 14 日：首次发布