B+树

B+树概况

• InnoDB使用了B+树索引模型
• 每个索引在InnoDB里面对应一棵B+树

B+树特点

• m阶B+树每个节点至多有m个子女
• 除根节点外，每个节点至少有[m/2]个子女，根节点至少有两个子女
• 有k个子树的中间节点包含有k个元素，每个元素不保存数据，只用来索引，所有数据都保存在叶子节点上
• 所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接
• B+树的查找，当索引部分某个节点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子节点为止。