Gbase 8s index b+ tree

         Database commonly used Index structure Yes Binary search tree 、B Trees ,B+ Trees 、Hash、 Bitmap and R Trees , One of the most widely used is B+ Trees . This section focuses on description B+ Tree index structure . B+ Trees can be seen as improved B Trees , Introducing B+ Before the tree , Let's take a look first B Index structure of tree , As shown in the figure .B The tree organizes the storage blocks into a tree , The tree is always in balance , That is, all leaf nodes always have the same depth .B There are three kinds of nodes in the tree ： The root node 、 Branch nodes and leaf nodes . The root node points to multiple branch nodes , Branch nodes point to leaf nodes , The leaf node points to the actual data row address .

         A tree m rank B A tree is a balanced one m Path search tree , Each storage block （ node ） Storage m Two keywords and m+1 A pointer to the . It's either an empty tree , Or a tree that satisfies the following properties .

1. The root node contains at least two child nodes , That is, at least two pointers are used , Each pointer points to B The next level of the tree stores blocks .
2. Always keep the data in order , The keywords in each storage block are arranged in ascending order .
3. The branch node must have at least （m +1）/2 Two pointers are used . Suppose that... Is used in a block j Key words , Set to K1,K2,…,Kj（K1＜K2＜…＜Kj）, Then this block has j +1 Two pointers are used , Each pointer points to B The next node in the tree . The first pointer points to the keyword less than K1 The recording part of , The second pointer points to a keyword greater than or equal to K1 And less than K2 The recording part of , And so on , The first j Pointers to keywords greater than or equal to Kj-1 And less than Kj The recording part of , The last pointer points to a keyword greater than or equal to Kj The recording part of .
4. In a leaf node, the last pointer points to the next leaf node to its right , That is, the next key is larger than its storage block . other m Pointers must have at least （m +1）/2 Used , Each pointer points to the actual data record . If the first j Two pointers are used , Then it points to the first in the block j Records of keywords .

         therefore , These nodes can be incompletely populated , The filling degree of each node （ That is, the number of keywords ） Must be greater than a minimum percentage value , The rest of the unfilled space is wasted .

        B This storage structure of the tree guarantees the search 、 The time complexity of insert and delete operations is in the logarithmic order . Recursively find from root to leaf nodes when searching , Will need to find the keyword and root node （ Branch nodes ） The keywords in are compared （ You can use sequential search or binary search ）, Find the interval where the keyword exists , Recursively find the next node according to the pointer , Until the leaf node , You can find the actual data row address pointed to by the leaf node . Insertion time ,B The tree grows from the bottom , When a node overflows （ There are more keywords than m individual ） when , Nodes are automatically split , The new node will be promoted to a higher level , When deleting, the operation is just the opposite .

         In order to further understand B Tree structure , The following is an example of a node split caused by inserting data , Pictured 8.5 Shown . It is assumed that each node can only store 4 Key words （m = 4）, Then when one is full 4 When a record is added to a node with keywords , The nodes will split , And promote the keywords in the middle to the upper level . Keyword promotion may cause the upper level nodes to continue to split , If the root node is full 4 Key words , Then the root node will split , A new root node will be created when the tree height is increased by one layer . After the split , There will be free locations in the nodes , You can use... When adding a new record .

         stay GBase 8s  In the database ,B+ The index structure of the tree is shown in Figure 8.7 Shown , Each inode is bi-directional , Both have pointers to the previous and next sibling nodes , In this way, you can query the range , Positive and negative searches can also be performed among peers , The performance of index in data search is greatly improved . The ability of a node to jump left or right to its sibling node is B+ A bright spot in the tree ,GBase 8s All non multidimensional data indexes in the database are B+ Tree index .