主页 > InnoDB存储引擎 > 剖析b+tree数据结构

剖析b+tree数据结构

小牛教程 InnoDB存储引擎 2021年06月16日

①索引树高度:2 (2-4层);

影响索引树高度因素:

。索引长度

。记录数

索引树高度不同消耗时间不同:

sata:300iops,0.0033 /io

2层:0.0033*2 单位是秒

3层:0.0033*3 单位是秒

②非叶子节点:保存键值(添加索引的字段的值)和指针

③指针:指针与数据页是一种映射的关系,通过指针就可以找到对应的数据页

④叶子节点:用于保存数据,保存所有记录的值,并经过排序

⑤双向指针(双向链表):用于保存相邻页的指针,提升范围查询效率

b+tree是平衡多叉树的数据结构,是基于页进行管理数据;

 

⑥:b+tree插入操作:(页旋转操作)

情况一:b+tree插入数据时,叶子节点没有满

直接插入到对应的数据页

情况二:b+tree插入数据时,叶子节点已满(产生页分裂 split)

先取出中间值,存放到上一层非叶子节点中;

情况三:b+tree插入数据时,叶子节点和上一层的非叶子节点都已满(产生两次页分裂操作)

⑦:b+tree删除操作

当叶子节点小于填充因子50%,就会发生页合并操作

广告位
标签: b+tree   mysql索引