响应式网站开发流行吗,网站开发会遇到哪些问题,wordpress如何删除目录,网站做弹窗广告B树B树又叫做二叉搜索树#xff0c;倒状的树形结构。如下图所示特点#xff1a;所有的非子夜节点最多拥有两个子节点树(左子树和右子树)。所有结点存储一个关键字。节点的左右儿子#xff0c;左边是比该节点小的#xff0c;右边是比该节点大的。缺点#xff1a;因为二叉搜… B树B树又叫做二叉搜索树倒状的树形结构。如下图所示特点所有的非子夜节点最多拥有两个子节点树(左子树和右子树)。所有结点存储一个关键字。节点的左右儿子左边是比该节点小的右边是比该节点大的。缺点因为二叉搜索树不存在平衡算法所以在某些特殊的情况下二叉搜索树等同于线性出现蹩脚的情况设计者们发现降低树的高度自然就可以提高查找效率。那么如何解决降低树的高度的问题在这种基础上设计者给二叉树加入了平衡算法出现了平衡树。二叉树搜索树的查询原理先从根节点开始和根节点匹配若是比根节点小就进入左子节点若是比根节点大进行右子节点依次按照这样的逻辑进行找到就返回。另一方面树的高度也会影响查询的效率设计者又是怎么解决的呢假设大规模数据存储中实现索引查询这样一个实际背景下树节点存储的元素数量是有限的即使存储在平衡二叉树中在大量数据的储存情况下这样导致二叉平衡查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁进而导致查询效率低下那么如何减少树的深度(当然是不能减少查询的数据量)一个基本的想法就是采用多叉树结构(由于树节点元素数量是有限的自然该节点的子树数量也就是有限的)。在这种前提下B-、B、B*也就是这样的数据结构多路搜索树不再是只有二路。所谓的平衡就是加上平衡算法在B树在经过多次插入与删除后有可能导致不同的结构极端一点就是出现线性的蹩脚树通过平衡算法(左旋和右旋)使树的节点分布均匀是树的查找算法等同于二分查找。所以对于树而言要提高查找的效率一个是保存平衡另一个是减少树的高度。B-树基于减少树的高度上B-树是一种多路搜索树并不是二叉的。如下图所示特点所有的非叶子结点最多有M个儿子(且M2)。根结点的儿子数为[2, M]其它非叶子结点的儿子数为[M/2, M]。每个结点存放至少M/2-1(取上整)和至多M-1个关键字(至少2个关键字)。非叶子结点的关键字个数指向儿子的指针个数-1。非叶子结点的关键字中从左到右由大到小排序。即A[1]非叶子结点的指针P[1], P[2], …, P[M]其中P[1]指向关键字小于K[1]的子树其它P[i]指向关键字属于(K[i-1], K[i])范围的子树最后一个指针P[M]指向大于随后一个关键字A[M-1]范围的值。关键字集合分布在整颗树中并且只会在节点中出现一次。搜索可能在非子叶节点或者子叶节点结束即非子叶节点也存储数据的身这个与B树有根本区别。所有叶子结点位于同一层。缺点当数据量大的时候不是依然会查询到最底层的叶子节点。这就是B-树的缺点但是相比B树而言已经优化了很多。B-树的性能总是等价于二分查找(与M值无关)也就没有B树平衡的问题。由于M/2的限制在插入结点时如果结点已满需要将结点分裂为两个各占M/2的结点删除结点时需将两个不足M/2的兄弟结点合并。B树B树是B-树的变体也是一种多路搜索树。如下图所示B基本与B-树同以下是与B-树的区别非叶子结点的指针与关键字个数相等而B-树的关键字指针个数-1指针P[i]指向关键字值属于[K[i], K[i1])范围的子树而在B-树是开区间。所有叶子结点增加一个指针指向下一个的兄弟叶子节点。所有关键字都出现在叶子结点的链表中(稠密索引)且链表中的关键字恰好是有序的搜索只会在叶子节点结束叶子节点存储所有关键字的值。不可能在非叶子结点命中非叶子结点相当于是叶子结点的索引(稀疏索引)叶子结点相当于是存储。B树与B树的区别所有的叶子节点包含了全部关键子信息及指向含有这些关键字记录的指针且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)。所有的非终端结点可以看成是索引部分结点中仅含有其子树根结点中最大(或最小)关键字。(而B树的非终节点也包含需要查找的有效信息)。这些链指针在链表中是有序存储的在搜索中能省大量的时间。那这些链指针可不可以加在所有的节点中呢答案是可以的除了根节点所有的节点都可以加上链指针。这就是B*树索引。B*树B*树是在B树的基础上在B树的非根和非叶子结点增加指向兄弟的指针将结点的最低利用率从1/2提高到2/3。特点B*树定义了非叶子结点关键字个数至少为(2/3)M即块的最低使用率为2/3(代替B树的1/2)在非根和非叶子结点增加指向兄弟的指针。B树与B*树的区别(1)B树的分裂当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。(2)B*树的分裂当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。结论所以B*树分配新结点的概率比B树要低空间使用率更高。关于回表查询比如select name from table where id?如果name没有索引那在查询的时候先得得到的是id对应这条数据所在的行数。拿着这个行数再去表中查询这条数据得到name字段。而拿着这个行数去得到name字段的动作就是回表查询。我们如何避免回表查询呢首先就是不要用 ” * “ 查询因为这时候会默认查询的字段没有索引必定进行回表查询。长按订阅更多面经分享
