T-reap索引构建与访问

实际上，索引提供的是指向存储在数据库中指定列中的数值的指针，然后根据指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行，这样可以使对应于数据库的程序语言执行得更快，可快速访问数据库中的特定信息。当表中有大量记录时，若要对表进行查询，目前通常采用全表检索或建立索引。全表检索，是将所有记录一一取出，和查询条件进行逐个比对，然后返回满足条件的记录，这样做优点是检全率比较高、差错少，缺点是会消耗大量数据库系统时间；建立索引，就是在表中进行条件检索，然后在索引中找到符合查询条件的索引值，优点是省时省力、效率较高，缺点是容易出现漏检的情况。总体来说，这两种方法各有利弊，但实践总要随着理论的创新不断突破，T-reap理论的出现为索引的构建带来了新的思路和方法，值得尝试。

本文采用的T-reap理论构建索引，索引表由索引关键词和索引地址构成，最终索引可以用数据页面的形式存储起来，以备查询。组织形式为自上而下建立，大树叶节点用以存放数据表，多个数据页生成一个中间节点的索引段，再由多个中间节点组成高级索引页面，以此类推直到高层Root-A层。这个过程中，高层索引页的值是下层节点中关键词库中的一员，可随时调用。为了方便在实际工作中的使用，这里笔者将完整的程序作了相应简化，具体程序如下：

一般来说，对于基于T-reap的索引访问，根据需要访问数据文件里的数据时，会有两种类型的I/O操作方式：①随机访问。即每次读取一个数据块，在实际程序中一般通过等待程序“db file sequential read”来完成；②顺序访问。即每次读取多个数据块，一般通过等待程序“db file scattered read”来实现。第一种方式则是访问索引里的数据块，而第二种方式的I/O操作属于全表扫描，等待程序可以根据实际获取物理I/O块的方式来命名的。事实上，T-reap索引虽然为一个树状的立体结构，但对应到数据文件里的相应排列，笔者更愿意将其形象化地转化为平面的形式，因为科研的目的就是要化繁为简，让人一看就懂。形象地展示出来也就是像下面这样：(www.xing528.com)

从上图就可以很清晰的看出来，当需要访问某个索引数据项的时候，首先从根节点开始，根据所要查找的数据，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据数据访问再下一层的分支节点，如此这般，直到访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前项的时候是不知道接下来应该访问哪个数据的。因此，在索引上访问数据块时，会对应到“db file sequential read”等待程序，其根源在于我们是按照顺序从一个索引项跳到另一个索引项，从而找到最终的索引项的。那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时就要访问所有的数据，因此唯一的问题就是尽可能高效地访问这些数据。因此，这时可以采用同步的方式，分步骤分批次获取多个数据。