MySQL索引的数据结构 一、什么是索引 索引就好比一本书的目录，通过书籍的目录可以快速找到我们想要的内容，同样的道理，索引是为了让我们更快找到想要的数据。
那么什么样的数据能够作为索引呢？索引是能把该记录限定在一定查找范围内的字段，也就是关键信息，比如说主键、唯一键、普通键。 二、索引的数据结构 mysql的索引采用的数据结构为B+树。 首先从二叉树说起。 二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。
二叉查找树（又名：二叉搜索树，二叉排序树），如下图每个节点存储关键字和指向子树的指针，图中的P1和P2就是执行子树的指针。 
一棵二叉树有如下性质，则称该二叉树为二叉查找树若任意节点的左子树不空，则左子树上所有节点的值均小于当前节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于当前节点的值；任意节点的左、右子树也分别为二叉查找树； 上面这棵二叉树不仅是二叉查找树，还是平衡二叉树，平衡二叉树的定义：任意一个节点的左右两个子树高度差都不超过一，就是平衡二叉树。 如果以二叉查找树作为索引，通常情况它查找时间复杂度为O(logn)。但是随着索引数据的变化，二叉查找树可能会退化为链表结构，查找的时间复杂度会退化为O(n)。 
B树是一种可以自平衡的树，能够保持数据有序，B树概括来说是一个一般化的二叉查找树，B树能保证它的查找效率是O(logn)。 如果每个节点最多有m个孩子那么这样的树就是M阶B树，如下图就是三阶B树。 
B树的定义如下：根节点至少包含两个孩子树中每个节点最多含有m个孩子（m>=2）除根节点和叶子节点外，其他每个节点至少有ceil(m/2)个孩子所有叶子节点都位于同一层假设每个非终端节点中包含有n个关键字信息，其中 a) Ki(i=1…n)为关键字即保存的值，且保存的值按顺序升序排序K(i-1) b)关键字的个数n必须满足：[ceil(m / 2)] <= n <=m-1 c)非叶子节点的指针：P[1], P[2], … P[M]; 其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1], K[i])的子树，即左边叶子节点小于左边节点，右边叶子节点大于右边节点。 注意：解释一下第三条性质，比如上图3阶B树，3/2=1.5，这里会舍弃小数位，也就是除了根和叶子节点，其他节点至少有一个孩子节点。 使用B树作为索引的目的是为了减少树的高度，能够存储更多信息，减少IO的次数。 在前面提到了，B+树是B树的变体，除了满足B树的基本定义之外，还满足以下性质：非叶子节点的子树指针与关键字个数相同非叶子节点的子树指针P[i],指向关键字值[K[i], K[i+1])的子树非叶子节点仅用来索引，数据都保存在叶子节点中。所有叶子节点具有一个链指针指向下一个叶子节点 B+树的大致结构如下，相比之下，B+树更适合做存储索引，相比于B树，它的高度会更“矮”，因此它的磁盘读写代价更低，B+树查询效率更加稳定，由于各个叶子节点都被顺序连接起来，这样做有利于对数据库的扫描。 
二、其他的索引实现方案 Hash索引 除了使用B+树来实现索引之外，还包含Hash索引，通过计算索引的hash值，在进行hash桶的个数取余计算，将具体的索引数据放到指定桶（bucket）上，如果出现hash碰撞则将碰撞的数据 以链表的形式保存，也可以实现索引。 不过Hash索引也有很多缺点，如：只能满足=或者in这种精确匹配，但是不能使用范围查询，因为hash值是无序的。同样也无法进行排序操作，并且不能避免扫描全表如果索引是一个复合索引如(name, id),我们无法使用name=xx条件，就没办法走索引，因hash值根据两个字段的值计算出来的。如果出现大量的Hash值碰撞，形成一个很长的链表结构，则Hash索引的性能就可能会很低下。 位图索引 目前只有Oracle实现了位图索引，它适合做那些可选择度不高的字段做位图索引，这种场景使用位图索引比较合适，比如说性别字段gender，1为男，0为女，就可以针对男女这两个关键字去做位图索引，如男的位图索引为010001，女的位图索引为，现在要查找所有男性数据，直接通过位图索引，就可以找到第二条和第六条数据为男性。 位图索引也有缺点，就是锁粒度大，一旦添加或者删除都会被锁住。 三、聚簇索引和非聚簇索引 MySQL有两种数据库引擎，即InnoDB和MyISAM。 在InnoDB 中，因为聚簇索引是和数据顺序相关的，所以只包含一个聚簇索引，即主键索引，如果主键索引不存在则使用唯一索引，如果都不存在，则使用mysql自动生成的一个隐藏的自增索引列作为聚簇索引。 那么聚簇索引有特点呢？聚簇索引不仅包含了索引值本身，还包含了该行数据的其他列信息。 其他的普通索引则为非聚簇索引，非聚簇索引则只包含了索引信息，如果需要查询其他信息，根据查找到的索引信息还需要回表进行二次查询，即通过聚簇索引再进行一次B+树查找，影响性能。 在MyISAM引擎中，所有的索引都是非聚簇索引。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/35113.html
