如何为半结构化数据集建立索引

最近遇到一个问题：大批量的文件，每个文件除了拥有类似于linux中struct stat中的一些基本的元数据外，还存在一系列的key/value对的扩展属性，现在的需求是，根据用户提供的key/value对，快速检索出匹配的文件集。

 

对于搜索来说，暴力搜索无疑是万能的，遍历所有的目标并逐个进行匹配，肯定能得出结果，比如linux下的find工具就是采用这种方式找出特定文件的。在匹配的过程中，查找目标可能由数值（整数、浮点数）或是字符串标示，对于数值可以通过直接比较的方式匹配，对于字符串，则可通过相关的字符串匹配算法(Brute-Force、kmp、正则表达式等)。

 

暴力搜索的缺点在于效率太低，当目标集较大时开销太大。通常解决的方法是为目标集针对搜索特性建立相关的索引，对于结构化数据（如数据库的应用）和非结构化的数据（如文本）采用的索引方式不同。

 

对于结构化的数据集（每个条目大小相同），如下图：

学号	名字	成绩
1001	Jack	90
1005	Rose	85
1006	Jim	95
1008	Sun	85
1012	Robin	70
1018	Lucy	90

 

数据集按学号顺序排列，如果需要查找某一学号对应的成绩，在没有任何索引的情况下，需要遍历整个数据集，为了提高效率，可为学号建立如下的索引（稠密索引，针对每一项建立一个索引项）。

 

学号	条目编号
1001	1
1005	2
1006	3
1008	4
1012	5
1018	6

 

由于学号是顺序存放的，当需要查找指定的学号时，可采用二分查找，将算法的时间复杂度降低到了logN。如果采用稠密索引时索引占用的存储空间过大，可采用稀疏索引的方式进行改善，如下图，每两项建立一个索引。

 

学号	条目编号
1001	1
1006	3
1012	5

 

在检索时，首先采用二分查找找到比目标小的最大的学号，然后从该学号起进行遍历，找出匹配的学号，算法时间复杂度为log(N/M)+ M(M为索引间隔)。

 

对于名字和成绩字段，可以采用相同的方式建立稠密索引，但因为其是无序的，不能建立稀疏索引。另外，还有很多种数据结构能加速结构化数据的查找，如为数据集的某个字段建立二叉查找树、B树、红黑树等以加速查找，多于一次需要查找多个属性的情形，可以采用KD-tree加速查找。

 

对于非结构化的数据集，比如说文档，建立索引的方式就完全不同了，搜索引擎就是干这个的，索引的方式大都采用倒排表，搜索引擎的相关原理以及索引的构建在我以前的博文http://blog.chinaunix.net/space.php?uid=20196318&do=blog&id=33938中介绍了。

 

对于本文开头提到的需求，其特性不像结构化数据那样规整，也不像非结构化数据那样分散，称其为半结构化的数据，google的bigtable系统主要用于半结构化数据的存储。大致模型相当于：每个对象拥有多种属性（bigtable中的列），很多对象可能拥有相同的属性（值不同）。

 

如何对半结构化的数据建立索引以加速查找，几经思索仍然没有头绪，希望与对此有兴趣的技术牛讨论交流，以发现并解决问题。