Mysql B+tree

mysql为什么使用B+tree

B+tree是B-tree的一个变种，在innodb中用的就是B+tree,主要是用在索引，比如innodb的聚集索引。

B+树非叶子结点只存储键值，大大滴减少了非叶子节点的大小，索引块能够存储更多的节点(每个节点就可以存放更多的记录),从磁盘读索引时所需的索引块更少，树更矮了,所以索引查找时I/O次数较B-Tree索引少，效率更高。

B+Tree在叶子节点存放的记录以链表的形式链接，范围查找或遍历效率更高，

b+树在同级节点间还存在一条连接，B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，如果要查询key为从a到b的所有数据记录，当找到a后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。