Gbase 8s index R tree

        R Trees can be seen as B The extension of tree in high dimensional space , Be similar to B Tree index ,R Tree indexes can also be used to organize data , Accelerate data access . It is designed for tables that contain multidimensional and spatial data types , It solves the problem of searching in high dimensional space . stay GBase 8s  This is used in the database R Tree index structure , It is mainly used to create indexes for the following data types ：

1. Spatial data containing multiple dimensions , Such as （X,Y） Geographic coordinate system ;
2. Additional time dimension data ;
3. Interval value , For example, time period data （9:00 P.M～9:30 P.M）;
4. A combination of multiple numeric types , It can also be regarded as multidimensional data value .

         In general , The database uses two fields (X,Y) To store the geographical location information of the museum , We need to traverse all the museums , Get its geographic location to calculate the distance , So as to get all the museums that meet the requirements . Without index , You need to traverse all the data rows in the table to calculate . If we create on this high dimensional spatial data R Tree index , Can greatly improve the search performance . Its idea is similar to B Trees , stay B The data in the tree is divided according to the size of the value , Organize the partitioned data into a tree for storage , and R Trees are used to segment spatial data , take B The tree method is effectively extended to high-dimensional space .

        R A tree is a multi fork balanced tree that stores high-dimensional data , Multiple rectangular areas are stored in each node , Every area I Corresponds to a pointer . Rectangular area in leaf node I An outer rectangle for a data object , And the pointer points to the area I Actual data row data contained in . Nonleaf node （ Root and branch nodes ） Rectangular area in I The outer rectangle of the rectangular area for all child nodes , And the pointer points to the child node at the next level , So all areas in the child node are in the area I Within the scope of .

 

         In order to achieve R Tree index , We use a minimum bounding rectangle to closely surround the spatial object ,R8 It is such a rectangular area , stay R8 Contains one or more spatial data objects , Divide all the data , All in all 12 The smallest rectangle （R8-R19） To surround all the data , They are stored in R In the leaf node of the tree , Each region has a pointer to the data objects contained in the region . Next, merge these smallest rectangular areas , Store in R In the upper node of the tree . We found that R8、R9 and R10 The three areas are closest , Merge them into a larger rectangular area R3 in , Empathy , This tree R In the tree branch node 5 Regions （R3～R7） Both contain the smallest rectangles in the leaf node , And each region has a pointer to the node of the next layer , Used to record several small rectangles contained in this area . Repeat the iteration process , Until all the data is stored in the largest areas of the root node （R1 and R2） until .

         And B Trees are like , A tree R Trees need to satisfy the following properties ：

1. The root node has at least two child nodes , Unless it is a leaf node ;
2. Except for the root node , Every node （ Branch nodes and leaf nodes ） Contained entities （ Rectangular area ） The number is between the minimum number of items m And the maximum number of items M Between , Usually m=M/2;
3. All leaf nodes are on the same layer ;
4. In a node , There is no order requirement for the arrangement of each entity .

         Here, the rectangular region in two-dimensional space can be extended to high-dimensional space .

        R Tree search 、 Insert and delete operations are similar to B Trees are like , Therefore, it can be effectively applied to the database .R The spatial regions corresponding to the sibling nodes of the tree can overlap , This makes it easier to insert and delete , But when searching, you may have to find multiple paths to get the final results , Therefore, the size of overlapping area has a great impact on the search efficiency .R+ Trees improve on this , The spatial regions corresponding to sibling nodes do not overlap .

        R A tree index is a dynamic index , in other words , When the data table is modified 、 When inserting and deleting ,R Tree indexes maintain their own data accordingly . in addition , Creating R Before tree index , We do not need to know the number or range of data in the index column , You can easily build R Tree index .