已经有了二叉搜索树以及他发展的红黑树和AVL数为什么还要优化出B树呢,我们知道红黑树的搜锁时间复杂度大约是AVL树的两倍左右,这点时间对于cpu来说无伤大雅,所以当红黑树储存10亿个数据以后她大概需要30次左右可以找到,这如果在内存中一下子就找到了,但是我们很多时候数据都是存在磁盘上的.这时找30次可就慢了.
计算机读取数据时从寄存器拿数据是最快的,然后是三级缓存,内存,再是磁盘,然后是云服务器上,他们越快成本越高空间就越小.所以一般个人计算机很多时候数据都是放在磁盘上,然而红黑树从磁盘拿数据就比较慢,因为需要30次不断进入磁盘拿数据,所以为了读取磁盘的次数少一点,就发明改进了平衡搜索树,于是有了B树,B树的高度更低.访问磁盘次数就更少.
B树又称多叉平衡搜索树.他不想二叉树那样每个节点最多有两个子节点,他可以有两个以上的子节点,所以他的搜索时间复杂度是log以度为底数据量为真数的对数函数的结果.
他有以下几条规则:
1:根节点至少有两个以上孩子.
2:每个非根结点有[m/2-1.m-1]个关键字(这里的除法都是向上取整).并有[m/2,m]个孩子.
3:根节点有[1,m-1]个关键字,[2,m]个孩子.
4:每个节点的关键字都是按升序排列.
5:所有的叶子节点都在同一层.
B树的只要构建方式是分裂,首先有一个根节点,不断往根节点中插入数据,一旦这个根节点满了就分裂出去一般的数据,存入另一个开好的空间.然后将分裂之前的关键字的中位数作为分裂的两个兄弟节点的双亲结点.以后所有的分裂都是这样的形式.如图:
B树的分裂过程就是如此,总是向上分裂者向兄弟节点分裂,当根节点满了以后就造出一个新的根节点.