一个适用于内存数据库系统的多维索引结构

A Multidimensional Index Structure for Main Memory Database System

树形结构一直都是数据库系统中建立多维索引最有效的方法之一,其中比较流行的有k-d树,R树等。但是对于内存空间极为宝贵的内存数据库来说,它们都有浪费内存的缺点。而T树作为内存数据库最常使用的一维索引结构,具有存取速度快,节约空间的优点,但是对于多维索引的情况它的效率却不高。该文首先介绍了k-d树,R树的特点及缺点,然后介绍T树的特点,操作和在多维条件下的缺陷,并提出了一种网格+T树的结构对其进行改进,从而使它适用于多维索引的情况。

Tree is one of the most effective method to build multidimensional index in database system,k-d-tree and R-tree are all some popular structures.But to the main memory database cherishing for the memory space,wasting memory is their shortcoming.T-tree is the most popularly used as one dimensional index structure.It uses less memory and access data fast,but it's efficiency is not high in the circumstance of multidimension.In this paper k-d-tree and R-tree's characteristic and shortcoming are introduced,then T-tree's characteristic,operation and it's shortcoming under circumstance of multidimension are also presented,at last we suggest a T-tree+grid structure to improve it,so as to it can fit the circumstance of multidimension.