mysql索引采用B+树结构的因素有哪些
发布时间：2022-01-14 11:05:20 所属栏目：MySql教程 来源：互联网
导读：这篇文章将为大家详细讲解有关mysql索引采用B+树结构的原因有哪些，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。 索引提高查询效率，就像我们看的书，想要直接翻到某一章，是不是不用一页一页的翻，只需要看下目录
|
这篇文章将为大家详细讲解有关mysql索引采用B+树结构的原因有哪些，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。 索引提高查询效率，就像我们看的书，想要直接翻到某一章，是不是不用一页一页的翻，只需要看下目录，根据目录找到其所在的页数即可。 在计算机中我们需要一种数据结构来存储这个目录，常见数据结构有哈希表，二叉查找树，二叉平衡树(AVL)，红黑树，那为什么Innodb和MyISAM选择b+树呢。 1. 哈希表 哈希表就是一个数组+链表，用下标0，1，2，3..... 表示其数据所在的位置。如果想要在哈希表中存放数据，首先用对这个数据进行散列算法（基本的就是取模运算），假如数组长度是13 ，进行模13之后是0-12，正好对应的数据的下标，如果计算出的下标一样的，就会在下标位置跟上链表。 缺点： 利用hash存储需要将所有的数据文件添加到内存，比较消耗内存空间。 hash的查找是等值查询，速度很快，但是各个数据间没有范围规律，但在实际工作中更多的是范围查询，hash就不太合适了。 不能直接说mysql不使用哈希表，而是要根据存储引擎来确定的，Memory存储引擎使用的就是哈希表 2. 二叉查找树 缺点： 造成树节点过深，从而增加查找的IO，而现在IO就是查找的瓶颈 3. 二叉平衡树-AVL 为了保持树的平衡，避免出现数据倾斜，需要进行旋转操作，通过左旋或者右旋最终保持最长子树和最短子树长度不能超过1，如果超过1就不是严格意义上AVL树了 缺点： 1.当数据量很大的时候，为了保持平衡，需要进行1-n次的旋转，这个旋转是比较浪费性能的，插入和删除效率极低，查询效率很高。 只有两个分支，数据量大的时候树的深度依然很深。 4. 红黑树 最长子树的不能超过最短子树的2倍，通过变色和旋转，在插入和查询上做了平衡 红黑树是avl树的变种，损失了部分查询性能来提高插入性能。 缺点： 同样是只有两个分支，数据量大的时候深度依然会很深 以上三种二叉树，随着数据的增多，最终都会出现节点过多的情况，而且他们有且仅有2个分支，那么IO的次数一样很多. 怎么解决仅有2个分支而且深度过深，这就有了B树，增加分支 5. B-Tree 首先不读B减树，读B树 所有键值分布在整棵树中。 搜索有可能在非叶子结点结束，在关键字全集内做一次查找，性能逼近二分查找。 每个结点最多拥有m个子树。 根节点至少有2个子树。 分支节点至少拥有m/2棵子树(除根节点和叶子节点外都是分支节点)。 所有叶子节点都在同一层，每个节点最多可以有m-1个key,并且以升序排列 每个节点占用一个磁盘块，一个节点上有两个升序排列的关键字和三个指向子树根节点的指针，指针存储的是子节点所在的磁盘块地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为16和34，p1指针指向的子树的数据范围小于16，p2指针指向的子树的数据范围为16-34，p3指针指向的子树的数据范围大于34。 （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号