用于提高数据库系统中的高速缓存性能的压缩方案

摘要

本发明揭示了一种高速缓存感知类型的R－tree，被称为CR－tree。为了把更多条目组合在一个节点内，CR－tree压缩MBR关键字，这些MBR关键字占用索引数据的主要部分。CR－tree首先相对于MBR的父母MBR的左下角来表示MBR关键字的坐标，以便从相对坐标表示中消除前导零。然后，CR－tree使用固定位数来量化相对坐标，以便进一步切掉尾随较低有效位。因此，CR－tree比普通R－tree宽得多和小得多，实验和分析结果表明，二维CR－tree执行搜索的速度比普通R－tree快，同时保持类似的更新性能，并耗用较少存储空间。

主权项

1.一种方法，用于提高对驻留在主存储器内的多维索引结构进行存取的高速缓存性能，以有助于查看存储在数据库中的数据对象，其中，索引结构包括：内部节点，其具有指向子女节点的指针；以及叶节点，其具有指向数据库对象的指针；该方法包括以下步骤：使最小边界矩形(“MBR”)与每个节点相关，其中，各MBR均是最小超矩形，其在叶节点情况下封闭相应数据对象，并在内部节点情况下封闭在子女节点内的所有超矩形；采用MBR的相对表示(“RMBR”)来逐个表示一个或多个所述MBR，MBR的相对表示是相对于一个参考MBR的坐标所表示的MBR的坐标；以及通过按照有限精度来量化各RMBR并在量化后切掉尾随无效位，把各RMBR压缩成量化RMBR(“QRMBR”)。