Mysql索引——索引结构3（扩展篇）-创新互联

目录

创新互联从2013年开始，是专业互联网技术服务公司，拥有项目网站设计、网站制作网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元邓州做网站,已为上家服务,为邓州各地企业和个人服务,联系电话:13518219792

1、关于Mysql数据结构选择合理性

1、全表遍历

2、HASH结构

3、二叉搜索树

4、AVL树（二叉平衡搜索树、自平衡二叉树）

5、B-tree （多路平衡查找树）

7、R树

附录：算法时间复杂度

---

1、关于Mysql数据结构选择合理性

从Mysql角度来说，不得不考虑的一个问题就是磁盘IO。如果我们能让索引的数据结构尽量减少磁盘IO操作，所消耗的时间就越小，可以说，磁盘IO操作次数对索引的使用效率至关重要。

查找都是索引操作，一般来说，索引非常大，尤其是关系型数据库，但数据量比较大的时候，索引的大小有可能几个G甚至更多，为了减少索引在内存的占用，数据库的索引是存储在外部磁盘上的。当我们利用索引查询的时候，不可能把索引全部加载到内存中，只能逐一加载，那么MySql衡量查询效率的标准就是磁盘IO次数。（把数据页加载到内存中，是非常耗时的，远比算法本身时间复杂读的计量维度要高）

1、全表遍历

。。。

2、HASH结构

哈希函数，又称为散列函数，它可以帮助我们大幅提升检索数据的效率。

哈希算法是通过某种确定性的算法(比如MD5、SHA1、SHA2、SHA3)，将输入转变为输出。相同的输入永远可以得到相同的输出，假设输入内容稍有微小偏差，在输出中通常有不同的结果。

比如：比较两篇文章是否相同，如果一个字一个字从头查到尾(遍历On)，效率就非常低，可以计算两篇文章内容的HASH值，直接比较二者hash值，得到是否相同，这样效率就大大提高。

加速查找速度的数据结构，常见有两类：

（1）树，例如平衡二叉树，查询/插入/修改/删除的平均时间复杂度 为 O(log2n)

(2)hash,例如HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1) //因为各个输入都有唯一输出，意思是位置是确定的，不需要通过查找，相当于一种映射思想

java的HashMap 去查找元素在HashMap的存储位置（输入key，得到value），本质是利用了HashCode的比较，这也解释了为什么HashMap里存入的对象，要重写hashCode(),

这样查找，不需要从数组或链表里遍历，而是通过计算出存入HashMap的元素的Hash值，直接计算出它的存放位置，所以时间复杂度为O1

采用Hash进行检索效率非常高，基本上一次就能查到要找的数据，而B+树需要自顶向下一次查找，多次访问节点才能找到数据，中间需要多次IO(把数据页加载到内存)，从效率上来说，HASH比B+tree更快。

在Hash方式下，一个元素k处于h(k)中，即利用Hash函数h，根据关键字k 计算出槽的位置。函数h将关键字映射到哈希表 T[0...m-1]槽位上。

#关于Hash冲突，以后再开文讲解。#

为什么会出现冲突？因为数组槽位是有限的，比如我们用取模运算，来作为Hash值计算的依据

h(k) =k%6

假设k1=13，k2=19.。取模6的结果都是 1 所以 k1和k2 出现了hash值相同的情况

上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：

Hash结构效率高，为什么索引结构还要设计成树型？

原因1：Hash索引仅能满足( = )   (<>)  和IN 查询，如果进行范围查询，哈希索引，时间复杂度会退为O(n); 而树型的“有序”特性，仍然可以保持O(log2n)的高效率。

原因2：Hash索引还有一个缺陷，数据的存储是没有顺序的，在Order BY的情况下，使用Hash索引还要对数据重排序。

原因3：对于联合索引的情况，Hash值是将联合索引键合并后一起计算的，无法对单独的一个键或几个索引键进行查询。

原因4：对于等值查询来说，通常Hash索引效率更高，但是也存在一个问题，就是索引列的重复值如果很多，效率就会降低。这是因为遇到Hash冲突时，需要遍历Bucket里的行指针来进行比价，找到关键字，非常耗时。所以Hash索引通常不会用到重复值多的列上，比如列为性别，年龄的情况。

Hash索引适用存储引擎如表所示：

索引 / 存储引擎	MyISAM	InnoDB	Memory
Hash索引	不支持	不支持	支持

Hash索引的适用性：

Hash索引存在很多限制，相比之下在数据库中B+tree 适用性会更广，不过也有一些场景采用Hash索引效率更高，比如在键值型数据库(K-V)  Redis存储的核心就是Hash表；

Mysql中的Memory存储引擎支持Hash储存，如果我们需要用到查询的临时表时，就可以选择Memory存储引擎，把某个字段设置成Hash索引，比如字符串类型的字段，进行Hash计算后，长度可以缩减到几个字节。当字段重复度低时，而且需要经常进行等值查询时，可以考虑采用Hash索引。

另外，InnoDB本身不支持Hash索引，但是提供了 自适应Hash索引(Adaptive  Hash Index)。什么情况下会用到自适应Hash索引呢？

如果某个数据经常被访问，当满足一定条件时，就会将这个数据页的地址存放到Hash表中。这样下次查询的时候，就可以直接找到这个页面所在的位置。这样让B+树也具备了Hash索引的优势。

（用Redis+SpringCache也可以实现相同的目的，当数据被频繁查找，但是很少进行修改时，可以将这些数据放入 Redis中缓存，一旦被修改，清空缓存。再次查询，再次缓存新数据，数据字典服务就是这么做的，详见 https://github.com/Chai-Feng/）

采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时 候，通过自适应 Hash 索引可以明显提高数据的检索效率。

我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

mysql>show variables like '%adaptive_hash_index';

3、二叉搜索树

如果以二叉树作为索引结构，那么，磁盘的IO次数和索引树的高度是相关的。

1、二叉搜索树的特点

• 一个节点只能有两个子节点，也就是一个节点的度不能超过2
• 左子节点<父节点;右子节点>=父节点，比我大的向右，比我小的向左

2、查找规则

我们先看一下最基础的二叉搜索树(Binary Search Tree) ，搜索某个节点和插入某个节点的规则一样，我们假设搜索插入的数值为Key

1、如果key大于根节点，则在右子树中进行搜索

2、如果key小于根节点，则在左子树中进行查找

3、如果Key等于根节点，也就是找到此节点，返回根节点即可

（参考二叉树的中序遍历，左--根--右）

比如我们对数列(32,34,89,5,23,77,91)创造出来的二分查找树如下：

（这其实是一棵 平衡二叉搜索树，查找的时间复杂度为Olog2n）

但是存在特殊情况，就是二叉树的深度非常大，比如我们给出的数据顺序是(5，22，23，34，77，89，91)

因为刚才说过，查找的效率，受制于 树的深度(磁盘IO次数) ，所以，我们要尽量减少树的高度。

把高瘦变成矮胖。

这时候，我们就考虑到平衡（二叉）树（任意节点的子树高度差小于等于1）

4、AVL树（二叉平衡搜索树、自平衡二叉树）

它是一棵空树或它的左右两颗子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树

这里说一下，常见的平衡二叉树有很多种，包括平衡二叉搜索树，红黑树、数堆、伸展树,平衡二叉搜索树是最早提出来的自平衡二叉搜索树，当我们提到平衡二叉树时，一般指的就是自平衡二叉搜索树。

数据查询的时间，主要依赖于磁盘IO次数，如果我们采用二叉树的形式，即使通过平衡二叉搜索树进行改进，树的深度也为Olog2n，当n比较大的时候，深度较高，比如下图：

因此，我们可以把结点的度加大(就是节点的分叉数)，把二叉树变成M叉树，这样可以降低树的深度。如下图，结点的度变成了3，树的深度由5 变成了 4.

5、B-tree （多路平衡查找树）

B树 Balance tree 。它的高度远小于自平衡二叉树的高度

（ceil函数  ceil(x) 返回大于等于x的最小整数 ）

一个 M 阶的 B 树（M>2）有以下的特性：

1. 根节点的儿子数的范围是 [2,M]。

2. 每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为 [ceil(M/2), M]。

3. 叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。

4. 假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]

5. 所有叶子节点位于同一层。

简单描述一下：

• 根据上图 磁盘块1为根节点，它有三个分叉，所以关键字个数范围是[ ceil(3/2),3]={2,3}，图中，关键字数为2个， 17，35。
• 中间层，根据关键字值的划分(都是按照升序排序)，17，35，可以划分成3个域，(<17),（17~35),(>35)，所以磁盘块2的关键字为根节点的第一个域（<17）8，12；磁盘块3为根节点关键字的第二个域(17~35) 26,30; 磁盘块4对于根节点的第三个域（>35）65,87。
• 同理，叶子节点也是如此构成。

然后我们来看下如何用 B 树进行查找。假设我们想要 查找的关键字是 9 ，那么步骤可以分为以下几步：

1. 我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；

2. 按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；

3. 按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

你能看出来在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比 较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行 比较所需要的时间要多，是数据查找用时的重要因素。 B 树相比于平衡二叉树来说磁盘 I/O 操作要少 ， 在数据查询中比平衡二叉树效率要高。所以 只要树的高度足够低，IO次数足够少，就可以提高查询性能 。

磁盘IO时间，和内存中因为比较，读取等消耗的时间(程序算法时间)，根本不是一个数量级，前者是后者的数百倍

小结：

1、B树在插入和删除结点的时候，如果导致树不平衡，就会通过自动调整节点的位置来保持树的自平衡

2、关键字集合分布在整棵树中，即叶子节点，和非叶子节点都存放数据，搜索有可能在非叶子节点结束。

3其搜素性能等价于在关键字全集内做一次二分查找。

再举例：

B+tree和B-tree的差异：

1、B+tree中，有K个孩子的节点，就有k个关键字。即孩子数量=关键字数，而B树中，孩子数=关键字数+1。

2、非叶子节点的关键字也会同时存在于子节点中，并且是在子节点中所有关键字中大(或最小)

3、非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中，而B树中，非叶子节点既保存索引，也保存数据记录。

4、所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字大小顺序连接。(在进行遍历的时候，B+树直接从叶子节点顺序遍历，但是B树要进行一次全树中序遍历)

面试可能会问到的一些问题：

思考题：为了减少IO，索引树会一次性加载吗？

1、数据库索引是存储在磁盘上的，如果数据量很大，必然导致索引大小也会很大，超过几个G

2、当我们利用索引查询时，是不可能将全部几个G的索引都加载进内存的，我们能做的只能是：逐一加载每个磁盘页，因为磁盘页对应索引树的节点

思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO

InnoDB存储引擎中页的大小为16KB，一般表的主键类型是INT(4字节)或BIGINT(8字节)，指针型一般为4或8个字节，也就是说一个页(B+tree一个节点)大概可以存储16KB/(8B+8B)=1K个键值(估算，为了方便取k为10^3）,也就是说一个深度为3的B+树索引 可以维护10^3*10^3*10^3=10亿条记录了。（此处假定一个数据页也存储10^3条行记录数据）

实际情况中，每个节点不可能填充满，因此在数据库中，B+tree 的高度一般在2~4层。Mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时，最多只需要进行1~3次磁盘IO(将数据页从磁盘加载致内存)。

思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？

1、B+tree的磁盘读写代价更低

B+树的内部结点并没有直响关键字具体信息的指针。因此其内部节点相对B树更小。如果把所有同一内部结点的关键字放在同一盘块中，那么盘块所能容纳的关键字数量越多，一次性读入内存中所需查找的关键字也就越多。相对来说，IO次数就降低了

2、B+树查询效率更加稳定

由于非终结点并不是指向文件内容的节点，而只是叶子节点中关键字的索引。任何关键字查询必须走完从根节点到叶子节点的路。所有关键字查询路径长度一致，所以每个数据查询效率相当。

但是B-tree 每个节点、关键字都会存储数据信息，导致不同关键字查询路径不同。

思考题：Hash 索引与 B+ 树索引的区别

1、Hash索引不能进行范围查询，而B+tree可以。这是因为HASH索引指向的数据是无序的，而B+tree的叶子节点是个有序链表。

2、HASH索引不支持联合索引的最左侧原则(即联合索引的部分索引无法使用)，而B+tree可以。对于联合索引来说，HASH索引在计算Hash值的时候，是将索引键合并，再一起就按Hash值，所以不会针对每个索引单独计算Hash值，因此如果用到联合索引的一个或几个索引值时候，联合索引无法被利用。

3、Hash索引不支持ORDER BY排序，因为HASH索引的数据是无序的，因此无法起到排序优化的作用，而B+树索引数据是有序的，可以起到对该字段ORDER BY 排序优化作用。

同理，我们也无法用Hash索引进行模糊查询(关键字可能不完整，HASH值不对)，而B+树使用LIKE进行模糊查询时候，LIKE后面的模糊查询可以优化作用。

4、InnoDB不支持Hash索引。

思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？

7、R树

R-Tree在MySQL很少使用，仅支持 geometry数据类型 ，支持该类型的存储引擎只有myisam、bdb、 innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果 没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记 录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满 足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度 地图这种超大数据库中，这种方法便必定不可行了。R树就很好的 解决了这种高维空间搜索问题 。它把B 树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解 结点的方法，保证树的平衡性。因此，R树就是一棵用来 存储高维数据的平衡树 。相对于B-Tree，R-Tree 的优势在于范围查找。

索引 / 存储引擎	MyISAM	InnoDB	memory
R-Tree索引	支持	支持	不支持

附录：算法时间复杂度

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站标题：Mysql索引——索引结构3（扩展篇）-创新互联
文章起源：http://cqcxhl.com/article/hchep.html