有关B树问题的浅研究

阿里面试的时候问了一个问题,数据库索引一般用的什么数据结构?B树!接着又问为什么用B树?查找速度比较快。再问:查找速度是比较快,但是为什么用B树,到这我知道我没给出他想要的答案。数据结构的东西本已经忘记的差不多了,但为了这个问题,我又把它翻了出来。

为什么使用B树?

一般情况下我们在考虑问题时,始终假设可以把整个数据结构存储到计算机的内存中的,但实际情况并不是这样,因为内存始终有限,当我们面对大的数据量时,就意味着我们的数据有很多必须是放在磁盘上的。

考虑算法效率的时候都会从算法的时间复杂度去出发。而在实际生产环境中,在涉及磁盘读取时,却更受制于磁盘的读取速度。一台机器运行指令的速率依赖的是电的特性,每秒大概执行指令5亿条,而读取磁盘则依赖磁盘的机械运动(当然固态硬盘是个例外),每秒读取120次左右,单独来看,好像还可以,但与执行指令的速度比起来,实在是太慢了。因此,当牵涉到I/O读取时,一个程序耗时绝大多数是在对数据的读取上。

一般我们用树时会考虑用二叉查找树。假如有1千万条数据,在最坏的情况下需要1千万次的磁盘访问。平均来看的话可能需要1.38logN次访问,大约是32次。而一棵典型随机构造的树,可能会有一些节点的深度会深3倍,大约需要100次的磁盘访问。如果用AVL树的多少会好一点,典型情形很是接近logN,但是这样也是需要大约25次的访问。那如果想把磁盘的访问次数减小到一个非常小的数。比如3或4。应该怎么办?

那一个直接的办法就是多加分支,如果均衡的话,对M分支的树可以把查找次数控制在LogN(底数为M,这边CDN有问题,MathJax加载不上,先这样了)这个程度,因此读取次数就会大大减小。而这就是我们所要B树的一个雏形。所以为什么使用B树?很明显。

B树需要满足的一些条件

对于一个M阶的B树,除了有M个分支以外,我们在此再加上一些条件:

  • 数据项存储在叶子上
  • 非叶结点存储直到M-1个关键字以指示搜索的方向,其中的关键字i代表子树i+1中的最小的关键字
  • 树的根或者是一片树叶,或者其儿子数在2到M之间
  • 除根外,所有的非树叶节点的儿子数在在M/2向上取整到M之间
  • 所有的树叶都在相同的深度上并有L/2向上取整到L之间个数据项(L为每个叶子结点存储的最大数据个数)

对于B树中的M及L的选取

那对于实际情况应该怎么选取M和L呢?
对于每个结点我们看成一个区块,且一个区块能容纳8192个字节,如果每个关键字使用32个字节,一条记录256个字节,对于一个非叶结点的分支(指示方向)为4个字节,这种情况下的M和L可通过计算得到。

一个非叶结点有M-1关键字,则关键字需要32M-32个字节,而每个分支有4个字节,非叶结点上有M个分支 ,需要4M个字节,因此一个非叶结点需要36M-32,使得其不超过8192的最大M为228,因此可以选择M为228,另每个记录数为256,则一个区块中可以存储32个记录,L=32。这种情况,在最坏情形下,树叶也只是在第4层。

Leo wechat
欢迎订阅公众号,建设中!