mysql 联合索引 数据结构是怎样的

如果是单索引,底层数据结构是B+ 树这点可以理解,但是如果是联合索引哪,搜了很久,感觉并没有明确的说明,
看到有篇文章讲到,但是 感觉文章是错误的 :
https://blog.csdn.net/weixin_...
疑惑关键点:

  • 每个非叶节点 都应该 包含了联合索引中的所有字段,而不是像这篇文章里说的 只包含第一个字段的索引信息。
  • 最左原则 在这样的B+ 树怎么体现

还有这篇:
https://use-the-index-luke.co...
这篇里讲的 每个非叶节点 包含了所有的字段,但是看起来并没有效果

阅读 7k
评论
    2 个回答


    http://hedengcheng.com/?p=577
    找到了答案:
    如图
    clipboard.png
    联合索引 bcd , 在索引树中的样子如图 , 在比较的过程中 ,先判断 b 再判断 c 然后是 d ,

      联合索引的分支块包含索引键值列以及相应的指针,但不是叶子块的所有键值都列举在分支块里,具体跟分支块的指针有关系:
      不管是联合索引还是单列索引,分支块都包含两种指针,一种叫LMC,另一种就是分支块的索引行对应的指针。
      1.LMC,left most child,每个分支块都会有一个,而且只会有一个,这个指针指向一个索引叶子块,这个LMC指针的特征是,所指向的叶子块,其所包含的索引键值的最大值,小于该分支块所有索引键值的最小值。例如分支的索引键值为(AD,AK,...),那么LMC所指向的叶子块的索引列值只能是排在AD前面的键值,例如AB,AC等;
      2.分支块的索引行对应的指针,首先明确,一个分支块指向多个叶子块,但并不是叶子块里的所有键值都列举在叶子块里。叶子块的内容除了上述说的LMC,其余的即是索引键值+对应的指针,而这个指针所指向的叶子块,其所包含的最小键值都要比该指针在分支块里对应的索引键值大。例如分支块的索引行是AD+指针,那么这个指针所指向的叶子块的最小键值必须比AD大,可以是ADF,可以是AK,但不能是AC。也就是说,分支块的每一个索引行对应的指针,都指向一个叶子块,且指向的叶子块的索引键的最小值,都比这个索引键值大。

      图就不画了,脑补吧~

        撰写回答

        登录后参与交流、获取后续更新提醒