MySQL --- 索引结构

MySQL --- 索引结构,第1张

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

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/web/2990408.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存