赞
踩
B Tree指的是平衡树,并且所有叶子节点位于同一层。
B+Tree是基于B Tree和叶子节点顺序访问指针进行实现,它具有B Tree 的平衡性,并且通过顺序访问指针来提高区间查询的性能。
在B+Tree 中,一个节点中的key从左到右非递减排列,如果某个指针的左右相邻key分别是key1和key2,且不为null,则该指针指向几点的所有key大于等于keyi且小于等于keyi+1.
与红黑树比较
红黑树等平衡树也可以用来实现索引,但是文件系统及数据库系统普遍采用B+Tree作为索引结构,因为:
1.查找次数更少
平衡树查找操作的时间复杂度跟树高h有关,o(h)=o(logdn),其中d为每个节点的出度。红黑树的出度为2【因为红黑树是二叉树】,而B+Tree的出度一般都非常的大,所以红黑树的树高h很明显比b+Tree大很多,查找的次数也就更多。
2.利用磁盘预读特性
为了减少磁盘I/O操作,磁盘并不是每次需要才去读取,而是会进行预读取。在预读取的过程中,磁盘进行顺序读取,顺序读取不需要进行磁盘寻道,并且只需要很短的磁盘旋转时间,速度会非常快。
【操作系统一般将内存和磁盘分割成固定大小的块区域,每一块称为一页,内存与磁盘以页为单位交换数据。】
【数据库系统将索引的一个节点的大小,使得一次I/O就能完全载入一个节点,并且可以利用预读特性,相邻的节点也能被预先载入】
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。