b+tree数据结构简述以及B+ Tree的存储结构

2020-08-01 10:58栏目:编程
TAG: java 算法

常用的索引模型有hash表 有序数组和搜索树
  • hash表就是数组 + 链表的散列接口 对指定的列进行hash查询到其在数组上的索引下标,然后value用于存储列名 + 主键id? hash表适用于只有等值查询的场景,不适合返回检索
b+ tree优点
  • 有序数组在等值查询和范围查询场景中的性能都很优秀。如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。所以有序数组索引只适用于静态存储引擎,比如你要保存的是2017年某个城市的所有人口信息,这类不会再修改的数据
  • 搜索树 -> 3.1 二叉树,这里不做说明,二叉树随着树高度的增加,检索效率急剧下降,而且需要持续保障树的结构,这个也在大数据量下造成效率低下。所以一般会想用到N叉树
基础知识:
  1. B+ Tree的最小存储单元是16KB,被称为页
  2. 散区是磁盘的最小存储单元 为512B
  3. 块是文件系统的最小存储单元,保存一个记事本,即使存储一个字符,也将占用4KB存储,所以块的最小存储单元为4KB
  4. 页是B+树的最小存储单元,16KB

B+ Tree的存储结构如下:

 
btree和b+tree的区别
P4 代表 < 4的区间 P5 代表 4<= P5 < 7 的区间 P6 代表 7 <= P6 < 10 的区间 P7 代表 >= 10的区间,从图中我们可以看到这个B+ Tree总共存储了5页的数据,其中Page(number = 3)用于存储索引数据,其他的用于存储元组数据(也就是行数据),这些都是存储硬盘上的,需要进行io载入内存
页就是B+Tree的最小存储单元。
上图应该还存在页与页之间的双向链表的关联关系,图没有展示出来。
其中还包含索引指针,也就是上图中的箭头,一般为6 byte,我们可以做一个计算,判断树高度为2的B+ Tree可以存储多少数据,比如单行数据为1KB, 索引主键用的是bigint 8 byte
因为页的存储单元为16KB 所以16 * 1024 = 16384 byte 所以第一页存储的索引数 + 索引指针个数为
16384 / (6 + 8) = 1170 个索引键(一般是范围存储) 1170对应第二级的1170个页
叶子结点存储数据 1170 * 16 / 1 = 18720 也就是说可以存储18720条数据
所以如果我们要查找主键为6的数据行,则需要进行2次磁盘io,第一次读取索引page,通过索引page再去读取4<= P5 < 7这个区间的页。

总结B+ Tree的特点:

非叶子节点不存储数据
每个页可以容纳更多的节点、直接减小树的深度,减小访问IO(和B-TREE作比较)
叶子节点存储数据(称这种索引为聚集或者聚簇索引)

备注知识点:

上图我们看到是主键索引,而非主键索引叶子节点也不存储数据,而是存储的的主键,叶子节点的页之间存在双向链表用于范围或者比较查找。
回表:对于非聚簇索引,他的叶子结点是存储主键的,所有查找到主键后,需要回表去走聚簇索引的查找流程。

上一篇:
线上数据cpu100%的问题解决方案

本文来自网络,不代表山斋月平台立场,转载请注明出处: https://www.shanzhaiyue.top