网站开发 外包,行业门户网站建站,wordpress novelist,网站设计 html5B树 前几篇文中讨论的数据结构我们都是假设所有的数据都存储在计算机的主存中。可说总要那么海量的数据需要通过个中数据结构去存储#xff0c;我们不可能有这么多内存区存放这些数据。那么意味着我们需要将他们放磁盘。所以这个时候范问时间复杂度O决定了他是否能适合存储磁盘…B树 前几篇文中讨论的数据结构我们都是假设所有的数据都存储在计算机的主存中。可说总要那么海量的数据需要通过个中数据结构去存储我们不可能有这么多内存区存放这些数据。那么意味着我们需要将他们放磁盘。所以这个时候范问时间复杂度O决定了他是否能适合存储磁盘大O模型不适用于磁盘存储。游戏规则变了。 在磁盘中操作速度和CPU内存计算速度相差甚远。 例如一台机器每秒可以执行5亿条指令。磁盘读写操作依赖磁盘的机械运动磁盘转动磁针移动也许磁盘7200RPM的转速1转大约1/120秒约8.3ms我们就估算是8.3每秒大概120次磁盘访问但是1分钟7200转比起每秒5亿简直不是一个量级比值相当于 40W1方法是尽量减少磁盘的操作宁愿大量计算对于树来说一个节点存在几个子节点我们在内存中通过指针寻址但是在磁盘中需要机械运动寻址
案例
我们通过一个案例来结束典型查找树的执行方式 假设要访问广东市所有人的出行记录。假设只有1kw项数据。每个关键字32字节是这个人的名字唯一id而一个记录存储这N个信息是256个字节。假设这些1kw数据不能都存储进主内存更具如上计算我们
解决方法 不平衡的二叉查找树解决如上问题完全不可取最坏情况他有线性深度从而可能需要1kw次磁盘的范问。平均的话一次成功的查找也需要1.38logN次范围由于log10000000 24 1.38*24 32/6 5秒。AVL树多少要好一点1.44logN是最坏情况平均访问是logN择优AVL计算平均25次磁盘查询一个数据4秒左右 要减少磁盘范问次数比如减到3,4。我们需要更加复杂的程序。因为机器指令相对机械操作相当于不耗时。以上分析我们知道二叉树不可行减少树层级增加节点分支的方式来解决。 31个节点的完美二叉树有5层31个节点的5叉树只有3层 一个完全二叉树的高度大概是log2N而一颗完全M叉树的高度大概是LogMN 我们建立与二叉树类似的M叉查找树二叉树中我们需要一个key来决定走左树还是右树M叉树我们需要M-1个key来决定 同时避免M叉树退化成链表我们需要给一个平衡条件限制M叉树退化到二叉树那就是B树如下性质 阶为M的B树是一颗具有下列特性的树 数据项存储在叶子节点上非叶子节点存储直到M-1个关键字用来指示搜索方向关键字i代表子树i1中最小关键字数的根节点如果不是叶子节点那么他子节点个数必须在2~M之间除了根节点外所有非叶子节点的子节点个数必须在M/2~M个之间所有叶子节点都在相同的深度上并且有L/2和L个数据项目L个数之后确认 如下图5阶B树的案例所有非叶子节点的儿子树都在3~5之间5/2 ~ 5 取整 3-5那么他们有2-4个关键字根可能只有2个子节点。这里我们L5所有叶子节点的数据项则是5/2 ~5 取整 3-5 之间 要求节点半满保证B树不退化到简单二叉树
B树结构分析
我们根据所存储的项的大小选择M与L的大小还是上面的案例我们假设一个区块的磁盘大小是8192Byte每个关键字32Byte在一颗M阶B数中有M-1个关键字那么总数是32M-1再加上M个分支指针int型4Byte总数则为32M-14M 36M-32那么一个片区8192可以存储的最大节点数据是8192 (36M-32) , M 228阶也就是我们每一层有228个分支以上案例中条件说一个记录256Byte8192/256 32 一个片区可以存储32个记录我们选择L32这样一个子节点中所有数据可以在同一个片区尽量一次磁盘操作可以读完这样我们保证了每个叶子节点有16~32个数据记录以及每个内部节点至少有228/2 114 中分支方式那么1kw个数据最多存储的叶子节点个数 10000000/16 625000 个叶子节点中层级最少情况每一层都是满分支228625000/228 224 /228 1最少的情况第二次就是叶子节点层级最多情况每一层都是半分支228/2114625000/114 5482.4/11448/1154 1 最多情况第四层是叶子节点如上分析最坏情况访问次数近似log(m/2)N给出
构造B树–添加节点删除节点
插入节点
我们按照上面图片中的案例需要将57 插入到图中的B树沿着树向下查找他不在树中我们把它作为第五项数据添加到第对应的叶子节点中如下图
方法一
如上更新数据分为三步 第一遍历B树找到插入数据的对应位置读取树叶节点中数据并且重排树叶节点中数据将重排的数据写入树叶节点 与磁盘的操作相比这些逻辑排列时间几乎可以忽略不计以上是简单的模式因为改树叶节点并没有被装满现在我们在插入55 到上图中。 55要插入的那个叶子节点已经满有L1项数据我们需要将他分成两个叶子节点这两叶子节点能保证所有需要的记录的最小个数每一个叶子节点3个项需要两次磁盘范问接着我们需要更新父节点将最小的值添加到父节点中需要一次写入的磁盘操作这种方式是更具上面L/2的规则执行虽然分离节点是耗时的至少需要2次磁盘操作但是很少发生比如我们上面L32 时候每次节点分裂时候都有16 或者17 项数据的两片叶子节点那么我们需要之后的17次添加操作才会有一次分裂 如上图情况当一个非叶子节点分裂父节点得到一个新的子节点父节点也需要增加一个项如果父节点此时也达到分裂阀值则需要继续向上分裂直到达到根节点。如果分裂根就得到两个根这显然不现实我们则创建一个新根这个根以分裂得到的两个新根为子节点所以我们的根节点的子节点的个数设置在2~M个是有这个原因的。这种方式也是B树增加高度的唯一方式
方法二
在相邻节点有空间时候将一个子节点交给邻节点例如将上图中29 节点插入到B树中我们可以把32移到 下一片树叶而腾出一个空间来这种方法要求对父节点进行修改因为这些关键字也会受影响他趋向于是的节点达到满节点更加节省空间。
删除节点
通过查找到要删除的项并在找到后删除他来执行删除操作问题在于如果被删元素的总元素个数已经低于最小值L/2那么删除后他的项目就不符合B树的要求我们可以通过在邻节点借一个节点来矫正这种情况如果邻节点也达到最小值L/2那么我们就合并这两个叶子节点结合成一个新的满叶节点。这种操作意味着父节点是去一个儿子如果失去儿子节点后又引发儿子节点数低于下限我们继续使用相同的策略一直到根节点如果这个过程使得根只剩下一个子节点那么删除这个根节点让原儿子节点当现在B树的新根节点。这种方式是B树降低高度的唯一方式。如下案例我们还是依照上图中的B数删除99 项的节点由于叶子节点只有两个而其邻节点以及是最小值3 个了因此我们将这两个叶子节点合并成有5项数据的一片新的叶子节点。结果他的父节点只有两个子节点此时父节点继续上一个步骤从邻节点领养邻节点有4个子节点最终使用双方都得到3个子节点如下图
上一篇数据结构与算法–AVL树原理及实现 下一篇数据结构与算法–图论最短路算法拓扑排序算法
