“Gird plus T Tree” index method for quick orientation in massive memory database
“Grid Plus T Tree” multidimensional index method in memory database partitions the whole record sets to different grid cells. Every grid data unit is connected with one data barrel, which loads records, through the grid directory. Every data unit is only mapped with one data barrel. For memory database, setting up a “T Tree” with these data units according to one field, so as to set up one “T Tree” for each data barrel according to one field. Then the grid directory can be presented by a k-dimensional (the dimension of keyword) array. The field ranges of these data units are called scale. Scale is the memory range of each “T Tree”. This invention successfully overcomes the shortcomings that the current index methods for memory database neither efficiently use the memory space nor suits multi-dimension. T Tree is much more efficient than K-D Tree or R Tree in using the memory space, and it has one more one-dimensional data structure during the process of grid partition, which can help store one field of the keyword as the index.
1. A grid plus T-Tree method to setup a multidimensional index for a memory database comprising the steps of:
partitioning whole record sets to different grid data units;
connecting every said grid data unit with one data barrel, which loads records, through a grid directory, every said grid data unit is only mapped with one data barrel;
setting up a T-Tree with said grid data units according to one field from memory database, so as to set up one T-Tree for each said data barrel according to one field;
presenting a grid directory by a k-dimensional array, where k is the dimension of the keyword array, the field ranges of said grid data units are called scale, said scale is the memory range of each said T-Tree.
2. The Grid Plus T-Tree method to set up multidimensional index for memory database of claim 1 , wherein said grid data unit is dynamically distributed in a memory database constituted by the dynamical distribution means said grid data units are stored in a memory space, which are previously partitioned during a initialization of the memory database, and is dynamically used or released according to requirements of a program.
3. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein for a disk database, generally one said data barrel is mapped with one disk page, a memory space occupied includes a space of array for setting up grid and building said T-Tree, if there is a k-dimensional index, <I1, I2 . . . Ik>, equably dividing its value scope into P1, P2 . . . Pk parts representatively by said scale, wherein I is each array of the k-dimensional array from I1 to Ik, P1, P2 . . . Pk is a value scope of each array.
4. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein partition value scope during partitioning said grid is a smaller key value, if it can be partitioned to 1, the larger scope shall be used as the index to set up said T-Tree.
5. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein all N records are partitioned to one grid, then there is only one T-Tree constructed in a memory space, and the time complexity is 0 (log2N); the normal situation is all the records are equably partitioned to every grid, then the record number of each grid is N/(P1*P2* . . . *Pk), and the time complexity is 0 (log2(N/(P1*P2* . . . *Pk))), wherein 0 is time complexity, N is the records in each grid.
6. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein a memory space occupied consists of the array space for setting up grid and the space for setting up T-Tree.
7. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein assuming there is a k-dimensional index <I1, I2 . . . Ik>, said their value scope are equably and respectively divided to P1, P2 . . . Pk parts by scale, then a memory space used to build grid is M1=C*P1*P2* . . . *Pk, within which C is the number of bytes for one address, if the operation system is of 32 bits, then C=4.
8. The Grid Plus T-Tree method to setup multidimensional index for memory database of claim 1 , wherein in nodes of the T-Tree record addressees are stored to instead of storing keywords, thereby a memory space is saved.