What is the data structure of mysql federated index
if it is a single index, it is understandable that the underlying data structure is a B+ tree, but if it is a joint index, it does not feel clearly explained after searching for a long time.
saw an article mentioned, but felt that the article was wrong:
https://blog.csdn.net/weixin_...
key points:
- each non-leaf node should contain all the fields in the federated index, rather than the index information that contains only the first field, as described in this article.
- how does the leftmost rule reflect in such a B+ tree
and this one:
https://use-the-index-luke.co...
each non-leaf node contains all the fields, but it doesn"t seem to have any effect
finds the answer in
http://hedengcheng.com/?p=577
:
as shown in the figure
joint index bcd, which looks like the picture in the index tree. In the process of comparison, judge b first and then d,
the branch block of the federated index contains the index key value column and the corresponding pointer, but not all the key values of the leaf block are listed in the branch block, which is specifically related to the pointer of the branch block:
whether it is a federated index or a single-column index, the branch block contains two pointers, one is called LMC, and the other is the pointer corresponding to the index row of the branch block.
1.LMC LMC left most child, each branch block will have one, and there will be only one. This pointer points to an index leaf block. This LMC pointer is characterized by that the maximum index key value of the leaf block it contains is less than the minimum value of all index key values of the branch block. For example, if the index key value of the branch is (AD,AK,...), then the index column value of the leaf block pointed by LMC can only be the key value in front of AD, such as AB,AC, etc.;
2. The pointer corresponding to the index row of the branch block, first of all, it is clear that a branch block points to multiple leaf blocks, but not all the key values in the leaf block are listed in the leaf block. Except for the LMC mentioned above, the rest of the leaf block is the index key value + the corresponding pointer, and the leaf block pointed to by this pointer contains a minimum key value larger than the corresponding index key value of the pointer in the branch block. For example, if the index row of a branch block is an AD+ pointer, then the minimum key value of the leaf block pointed to by this pointer must be greater than AD, which can be ADF, AK, but not AC. In other words, the pointer corresponding to each index row of the branch block points to a leaf block, and the minimum value of the index key of the leaf block is larger than the index key value.
Let's not draw the
picture, let's make up for it.
