天津做网站的公司怎么样,自己做网站需要什么技术,网站开发技术发展趋势,本地电脑做网站B-树B-树是一种多路搜索树#xff08;并不一定是二叉的#xff09;1970年#xff0c;R.Bayer和E.mccreight提出了一种适用于外查找的树#xff0c;它是一种平衡的多叉树#xff0c;称为B树#xff08;或B-树、B_树#xff09;。一棵m阶B树(balanced tree of order m)是一…B-树B-树是一种多路搜索树并不一定是二叉的1970年R.Bayer和E.mccreight提出了一种适用于外查找的树它是一种平衡的多叉树称为B树或B-树、B_树。一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树或者是满足下列性质的树1、根结点至少有两个子女2、每个非根节点所包含的关键字个数 j 满足┌m/2┐ - 1 j m - 13、除根结点以外的所有结点不包括叶子结点的度数正好是关键字总数加1故内部子树个数 k 满足┌m/2┐ k m 4、所有的叶子结点都位于同一层。特点是一种多路搜索树并不是二叉的1.定义任意非叶子结点最多只有M个儿子且M22.根结点的儿子数为[2, M]3.除根结点以外的非叶子结点的儿子数为[M/2, M]4.每个结点存放至少M/2-1取上整和至多M-1个关键字至少2个关键字5.非叶子结点的关键字个数指向儿子的指针个数-16.非叶子结点的关键字K[1], K[2], …, K[M-1]且K[i] K[i1]7.非叶子结点的指针P[1], P[2], …, P[M]其中P[1]指向关键字小于K[1]的子树P[M]指向关键字大于K[M-1]的子树其它P[i]指向关键字属于(K[i-1], K[i])的子树8.所有叶子结点位于同一层如M3B-树的搜索从根结点开始对结点内的关键字有序序列进行二分查找如果命中则结束否则进入查询关键字所属范围的儿子结点重复直到所对应的儿子指针为空或已经是叶子结点B-树的特性1.关键字集合分布在整颗树中2.任何一个关键字出现且只出现在一个结点中3.搜索有可能在非叶子结点结束4.其搜索性能等价于在关键字全集内做一次二分查找5.自动层次控制B树B 树是一种树数据结构是一个n叉树每个节点通常有多个孩子一棵B树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点也可能是一个包含两个或两个以上孩子节点的节点。用途B 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B树作为元数据索引。B 树的特点是能够保持数据稳定有序其插入与修改拥有较稳定的对数时间复杂度。B 树元素自底向上插入。B树的定义B树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B树和m阶的B-树的差异在于1.有n棵子树的结点中含有n个关键字每个关键字不保存数据只用来索引所有数据都保存在叶子节点。2.所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。3.所有的非终端结点可以看成是索引部分结点中仅含其子树根结点中的最大或最小关键字。 通常在B树上有两个头指针一个指向根结点一个指向关键字最小的叶子结点。B树是B-树的变体也是一种多路搜索树1.其定义基本与B-树同除了2.非叶子结点的子树指针与关键字个数相同3.非叶子结点的子树指针P[i]指向关键字值属于[K[i], K[i1])的子树B-树是开区间5.为所有叶子结点增加一个链指针6.所有关键字都在叶子结点出现如M3B的搜索与B-树也基本相同区别是B树只有达到叶子结点才命中B-树可以在非叶子结点命中其性能也等价于在关键字全集做一次二分查找B的特性1.所有关键字都出现在叶子结点的链表中稠密索引且链表中的关键字恰好是有序的2.不可能在非叶子结点命中3.非叶子结点相当于是叶子结点的索引稀疏索引叶子结点相当于是存储关键字数据的数据层4.更适合文件索引系统B*树是B树的变体在B树的非根和非叶子结点再增加指向兄弟的指针B*树定义了非叶子结点关键字个数至少为(2/3)*M即块的最低使用率为2/3代替B树的1/2B树的分裂当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针B*树的分裂当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针所以B*树分配新结点的概率比B树要低空间使用率更高小结B-树多路搜索树每个结点存储M/2到M个关键字非叶子结点存储指向关键字范围的子结点所有关键字在整颗树中出现且只出现一次非叶子结点可以命中B树在B-树基础上为叶子结点增加链表指针所有关键字都在叶子结点中出现非叶子结点作为叶子结点的索引B树总是到叶子结点才命中B*树在B树基础上为非叶子结点也增加链表指针将结点的最低利用率从1/2提高到2/3B-树,B树,B*树 总结对比首先注意B树就是B-树-是个连字符号不是减号。 B-树是一种平衡的多路查找(又称排序)树在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance) B树有一个最大的好处方便扫库B树必须用中序遍历的方法按序扫库而B树直接从叶子结点挨个扫一遍就完了。 B树支持range-query(区间查询)非常方便而B树不支持。这是数据库选用B树的最主要原因。 比如要查 5-10之间的B树一把到5这个标记再一把到10然后串起来就行了B树就非常麻烦。B树的好处就是成功查询特别有利因为树的高度总体要比B树矮。不成功的情况下B树也比B树稍稍占一点点便宜。 B树的优势是当你要查找的值恰好处在一个非叶子节点时查找到该节点就会成功并结束查询而B树由于非叶节点只是索引部分这些节点中只含有其子树中的最大(或最小)关键字当非终端节点上的关键字等于给点值时查找并不终止而是继续向下直到叶子节点。因此在B树中无论查找成功与否都是走了一条从根到叶子节点的路径。 有很多基于频率的搜索是选用B树越频繁query的结点越往根上走前提是需要对query做统计而且要对key做一些变化。 另外B树也好B树也好根或者上面几层因为被反复query所以这几块基本都在内存中不会出现读磁盘IO一般已启动的时候就会主动换入内存。 mysql底层存储是用B树实现的因为内存中B树是没有优势的但是一到磁盘B树的威力就出来了。 B*树 是B树的变体在B树的非根和非叶子结点再增加指向兄弟的指针B*树定义了非叶子结点关键字个数至少为(2/3)*M即块的最低使用率为2/3代替B树的1/2 B树的分裂当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针 B*树的分裂当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针 所以B*树分配新结点的概率比B树要低空间使用率更高
