B+树页节点结构
img
将所有的记录分组,每组都会存储多条记录
页目录存储的是㯾(slot),㯾相当于分组记录的索引,每个㯾指针都指向每个分组的最后一条记录。...因此页目录中提供了二分查找,来提高检索的效率
B+树的检索过程
从B+树的跟开始,逐层找到叶子节点
找到叶子节点对应的数据页,将数据页加载到内存中,通过页目录的㯾大致找到数据所在的分组
在分组中通过聊表的遍历找到记录...下面是一颗标准的红黑树
img
红黑树与AVL树相比,红黑树的查询效率会有所下降,这是因为树的平衡性变差,高度更高。...从磁盘中读取数据时,都是按磁盘块来读取的,并不是一条一条读的,如果我们尽可能多的把数据放进磁盘块中,那么一次磁盘读取就会读取更多的数据,那么查询数据的时间也就会降低。...B+树所有的数据均存储在叶子节点,而且数据是按照顺序存放的。
使用B+树进行范围查找,顺序查找,分组查找,去重相当容易,因为B+树的数据是按顺序存放的。而B树的数据分散在每个节点,要实现这一点很困难。