记录一下对B+ TREE的简单理解
mysql索引笔记:
常用的索引模型有hash表 有序数组和搜索树
- hash表就是数组 + 链表的散列接口 对指定的列进行hash查询到其在数组上的索引下标，然后value用于存储列名 + 主键id? hash表适用于只有等值查询的场景，不适合返回检索
- 有序数组在等值查询和范围查询场景中的性能都很优秀
如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以有序数组索引只适用于静态存储引擎，比如你要保存的是2017年某个城市的所有人口信息，这类不会再修改的数据 - 搜索树 -> 3.1 二叉树，这里不做说明，二叉树随着树高度的增加，检索效率急剧下降，而且需要持续保障树的结构，这个也在大数据量下造成效率低下。所以一般会想用到N叉树
- 基础知识：
- B+ Tree的最小存储单元是16KB,被称为页
- 散区是磁盘的最小存储单元 为512B
- 块是文件系统的最小存储单元，保存一个记事本，即使存储一个字符，也将占用4KB存储，所以块的最小存储单元为4KB
- 页是B+树的最小存储单元，16KB
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作比较）
- 叶子节点存储数据（称这种索引为聚集或者聚簇索引）
备注知识点:
-
上图我们看到是主键索引，而非主键索引叶子节点也不存储数据，而是存储的的主键，叶子节点的页之间存在双向链表用于范围或者比较查找。
-
回表：对于非聚簇索引，他的叶子结点是存储主键的，所有查找到主键后，需要回表去走聚簇索引的查找流程。
未完待续。。。