MySQL --- 索引结构

文章目录 mysql索引索引的优缺点索引的分类索引的创建 索引的数据结构B-Tree 多路平衡查找树B+TreeB+树索引Hash索引面试题

mysql索引

索引（index）是高效获取数据的数据结构(有序)。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

索引的优缺点

优点：1、提高数据检索的效率，降低数据库的IO成本。2、通过索引对数据进行排序，降低数据排序的成本，减低CPU的消耗。

缺点：1、索引列也是要占用空间的。2、索引降低了更新表的速度，读对表进行insert ,update,delete时，效率降低。

索引的分类

分类	含义	特点	关键字
主键索引	针对于表中主键创建的索引	默认自动创建，只能有一个	primary
唯一索引	避免同一个表中某数据列中的值重复	可以多个	unique
常规索引	快速定位特定的数据	可以多个
全文索引	全文索引查找的是文本中的关键词，不是比较索引中的值	可以多个	fulltext

在InnoDB的存储引擎中，根据索引的存储形式，可以分为以下两种：

分类	含义	特点
聚集索引	将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据	必须有，且只有一个
二级索引	将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键	可以存在多个

聚集索引比二级索引的速度更快

聚集索引选取规则:
如果存在主键，主键索引就是聚集索引。
如果不存在主键，将使用第一个唯一(UNIQUE）索引作为聚集索引。
如果不存在主键，或没有合适的唯一索引，则InnoDB会自动生成一个rawid作为隐藏的聚集索引。

索引的创建

# 创建普通索引
create index idx_user_name  on  tb_user(name); 
# 创建唯一索引    
create  unique index idx_user_phone  on tb_user(phone);   
# 创profession,age,status联合索引
create index idx_user_pro_age_sta on tb_user(profession,age,status) ;    

索引的数据结构

MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种：

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持
Hash索引	底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询
R-Tree索引（空间索引）	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，使用较少
Full text(全文索引)	是一种通过建立倒排索引，快速匹配文档的方法

B-Tree 多路平衡查找树

度(Degree)-节点的数据存储个数，每个树节点中数据个数大于 15/16*Degree（未验证） 时会自动分裂，调整结构。
每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
根节点至少包括两个孩子 树中每个节点最多含有m个孩子( m>=2 ) ，除根节点和叶节点外，其他每个节点至少有ceil(m/2)个孩子
所有叶子节点都位于同一层，即根节点到每个叶子节点的长度都相同 每个节点都有索引和数据，也就是对应的Key和value值。

B+Tree

B+树是B树的变体，其定义基本与B树相同
区别：1、所有的数据都会出现在叶子节点。2、叶子节点形成一个单向链表。

B+树索引

mysql索引数据结构对经典的B+tree进行了优化，

在原B+tree的基础上，增加一个指向相邻叶子节点的链表指针，形成了带有顺序指针的B+Tree，提高区间访问的性能。

B+Tree存储结构，只有叶子节点存储数据
新的B+树结构没有在所有的节点里存储记录数据，而是只在最下层的叶子节点存储，上层的所有非叶子节点只存放索引信息，这样的结构可以让单个节点存放下更多索引值，增大度Degree的值，提高命中目标记录的几率。

Hash索引

hash索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽上，存储在hash表中、如果产生hash冲突，可以通过链表解决。

只有Mermory存储引擎支持，innodb中具有自适应hash功能

特点：

Hash索引只能用于对等比较(=，in)，不支持范围查询(between,order by,>,<,…)无法利用索引完成排序操作
3．查询效率高，通常只需要一次检索就可以了，效率通常要高于B+tree索引（除非大量Hash值相等时索引）不能利用部分索引建查询不能避免表扫描

面试题

为什么InnoDB存储引擎选择B+tree索引结构呢？

相对于二叉树，层级更少，搜索效率高;
对于B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的心高度，导致性能降低;所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
相对于hash索引，B+tree支持范围匹配及排序 *** 作

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

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

2、B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的节点，而只是叶子结点中关键字的索引。所有任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当