深入理解B树、B+树及B*树的数据结构与应用场景

参考地址:这,这,这,这里
B树即B-树.B表平衡的意思.B树必须中序遍历,B&＃43;树,则叶子扫一遍即可.B&＃43;树支持区间查询.
*号,要放在反引号里面
定义:
有个阶数,即最大子节点数m. 关键字,从小到大排列.每个节点,存储键和值. 叶子节点,位于同一层. 每个关键字的左子树的关键字都小于自己,而右子树的关键字都大于自己.这一条所有的树都应该这样,为了二分法快速查找. 根节点子节点数为[2,m].其余为[m/2,m]节点数 节点,至少有(m-1)/2个关键字,至多m-1个.根节点至少1个关键字(2个子节点).注意这是关键字.m是最大子节点数. 注意区别关键字与子节点数.关键字&＃61;子节点数-1.
B树插入:
如果,关键字

其实,整个B树与B&＃43;树,B*树,所有二叉树,所有树,都是在实数上的.
他们的调整就是调整附近位置.再满足他们自己的限定条件.他们的位置无论如何调整,始终都是垂直不变的. 看起来调整了,不过是上下级的变化.他们的根本位置是不变的.因为他们都是实数上数值.根本就没变.

区间查询(数据库有用):查询5~10这个区间.B&＃43;树左边一个点,右边一个点,一把索.B树成功查询方便,因为节点短.
B&＃43;树的子节点(叶位置)都是连在一起的.所以可以一把索.相当于每个叶子的值都是手拉手的在实数上排列着的.
B树B&＃43;树的上层,其实因为经常查找,所以,都在内存缓冲着的.
B*树,在非根与非叶子节点处,再加上指向兄弟的指针.这样,兄弟也链接上了.即非叶子节点也相互手拉手了.
B*树,非叶子节点,>2m/3.
B&＃43;的&＃43;就是叶子结点是连着的.
B&＃43;树分裂:
分配新结点,复制原结点一半数据过去,父结点增加新结点指针,只影响父,新结点,不影响兄弟结点
B*数分裂:
先看兄弟结点,如未满,则一部分至兄弟结点,调整兄弟节点,再调整自己节点. 如满了,在原结点与兄弟结点中加新结点,各复制1/3数据过去,在父节点中增加新节点指针.
需要兄弟结点,所以,要有兄弟结点的链接指针,因而*就是叶子节点加上兄弟结点的意思.
也有基于频率的B树.
二叉树比二分查找的优点是:改变结构时,只需要常数开销.,即方便增删.
平衡算法,保持插入后,树仍然是平衡的.
B树的节点与关键字的关系是:节点 关键字 节点 关键字 节点...的关系.
子节点,可能为空.即无内容的节点.
B树性能等价于二分查找.节点满时分裂成2个子节点,删结点时,不足时,要合并节点.
B*树,和另外一个节点,满足2/3时,分节点,不足时,合并结点.
B&＃43;树.从根部的节点的关键字,最终都压扁下放到叶子节点.,B&＃43;树就是非叶子结点,只起一个判定作用.叶子节点一层才是所有数据,从头到尾装满了实数线.更适用于文件索引.
B*树,B树再加上兄弟节点的指针,主要是为了更节省空间