MySQL数据库索引选择使用B+树的原由是什么
发布时间：2022-02-09 20:35:23 所属栏目：MySql教程 来源：互联网
导读：这篇文章主要介绍MySQL数据库索引选择使用B+树的原因是什么，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！ 一、二叉查找树 （1）二叉树简介： 二叉查找树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下
|
这篇文章主要介绍MySQL数据库索引选择使用B+树的原因是什么，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！ 一、二叉查找树 （1）二叉树简介： 二叉查找树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下性质： 1、任意节点左子树不为空,则左子树的值均小于根节点的值； 2、任意节点右子树不为空,则右子树的值均大于于根节点的值； 3、任意节点的左右子树也分别是二叉查找树； 4、没有键值相等的节点； 对上述二叉树进行查找，如查键值为5的记录，先找到根，其键值是6，6大于5，因此查找6的左子树，找到3；而5大于3，再找其右子树；一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需求3次。用同样的方法在查找键值为8的这个记录，这次用了3次查找，而顺序查找需要6次。计算平均查找次数得：顺序查找的平均查找次数为（1+2+3+4+5+6）/ 6 = 3.3次，二叉查找树的平均查找次数为（3+3+3+2+2+1）/6=2.3次。二叉查找树的平均查找速度比顺序查找来得更快。 （2）局限性及应用 一个二叉查找树是由n个节点随机构成，所以，对于某些情况，二叉查找树会退化成一个有n个节点的线性链。如下图： 大家看上图，如果我们的根节点选择是最小或者最大的数，那么二叉查找树就完全退化成了线性结构。上图中的平均查找次数为（1+2+3+4+5+5）/6=3.16次，和顺序查找差不多。显然这个二叉树的查询效率就很低，因此若想最大性能的构造一个二叉查找树，需要这个二叉树是平衡的（这里的平衡从一个显著的特点可以看出这一棵树的高度比上一个输的高度要大，在相同节点的情况下也就是不平衡），从而引出了一个新的定义-平衡二叉树AVL。 二、AVL树 简介 AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。 （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号