B+Tree

定义

B+Tree区别于B-Tree的几点在于：

1. 非叶子节点只储存关键字信息不包含记录数据
2. 叶子节点形成了一个双向链表
3. 数据记录都存放在叶子节点中

优势

区别于B-Tree，InnoDb存储引擎每个页大小为16KB，而一个关键字信息加上指针信息一般为16B，但是每个关键字还包含着对应的记录的信息，这部分大小不定，可知InnoDb一次读取的磁盘块大概包含16KB/16B=1k（估值），所以每个节点都可以存储1000个关键字，对于一个3阶的B+Tree，大概可以维护10^3 * 10 ^3 * 10^3,大概有10亿条记录，然而它的随机查询需要的io操作只需要3次