MySQL索引B+树数据结构

看了下MySQL InnoDB索引,十分好奇这个B+Tree数据结构如果是类定义,这个class应该如何来写,简单了解一下,满足一下好奇心

下面两个链接,可以自行手动创建操作B+Tree的动态图,十分直观:

B+Tree Visualization

JavaScript B+ Tree

首先看下B-Tree,定义的一堆条件可以google,与B+Tree最大的不同是,B-Tree所有节点里都有key和value

依次插入的节点对应的key为:6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

得到的四阶B-Tree如下

NewImage

下面有一个完美的动态图画出了整个流程

接着下面是B+Tree,这才是InnoDB索引的数据结构,而B+Tree所有的数据value都存在了叶子节点上,非叶子节点是不会存储数据的

依次插入的节点对应的key为:6 10 4 14 5 11 5 15 3 2 12 1 7 8 8 6 3 6 21 5 15

得到的四阶B+Tree如下

NewImage

同样动态图如下

如果想知道B-Tree和B+Tree插入,删除的详细逻辑,这里有一篇十分详细:B树和B+树的插入、删除图文详解

这里我更关心的是放在源码里的类定义,可以github里检索BPlusTree相关类定义,各种语言描述都有

https://github.com/search?utf8=%E2%9C%93&q=BPlusTree&type=

在MySQL中,表都根据主键顺序以索引的形式存放,建表的时候就已经创建,假如又创建一个其它字段的索引,那么就会创建一棵新的B+Tree,因此总结一下:

1、如果有多个索引,那么每个索引在InnoDB里都对应了一棵B+树

2、如果是主键索引,B+树叶子节点里数据存的是表的整行数据

3、如果是非主键索引,B+树叶子节点里数据存的是主键的值

因此对于select * from table where k=1这条sql语句:

1、如果k是主键,只需要搜索k索引这棵B+树,就能得到结果

2、如果k不是主键,就可以先搜索k索引这棵B+树,得到对应主键的值,然后再搜索主键B+树,得到结果

发表评论