磁盘区间树批量更新方法

摘要

本发明提供了磁盘区间树批量更新方法，应用于数据库领域，同步实时数据和磁盘区间树索引更新。本发明所述的磁盘区间树批量更新方法是通过对数据区间的预处理，将所有区间分为内区间集合和外区间集合，再分别对两类集合采用内区间更新和外区间更新技术，将结果保存至磁盘中的平衡区间树中。这种索引更新方法能处理当区间范围超出设定最大值范围的情况，当新结点导致区间树不平衡时，也可通过旋转平衡变换进行调整。同时由于每次是以结点为单位对区间树进行更新，因此避免将区间依次写入磁盘，降低了磁盘访问次数，大量减少I/O和CPU开销，提高了索引更新效率。

主权项

磁盘区间树批量更新方法的总体特征是通过对区间数据做预处理，将区间集合划分为内区间集合和外区间集合两个部分。对于内区间集合遍历磁盘区间树，找到每个区间应插入的结点位置，对磁盘区间树的结点进行更新；而对于外区间集合，为该集合内所有区间新建立一棵区间树，将新区间树的结点依次插入到磁盘区间树中。这个技术大量减少了磁盘访问次数，降低I/O和CPU开销，提高了索引更新效率。其过程由以下三部分构成：(1)区间预处理：将需要实时更新的区间数据根据磁盘区间树的最大端点值，分为内区间集合和外区间集合；(2)内区间更新：由(1)中得到的内区间集合作为输入，遍历一次磁盘区间树，找到各个区间应插入的相应结点位置，以结点为单位对磁盘区间树进行更新操作；(3)外区间更新：由(1)中得到的外区间集合作为输入，为集合中的区间建立一棵新的平衡区间树，建树完成后，将新树中的所有结点依次插入到磁盘区间树中，得到更新后的磁盘区间树。