认识Mysql索引

索引

索引就是一种快速检索的、排好序的数据机构。

本质:数据结构+算法

类别及数据结构

Hash表

能够快速查找O(1),但是会发生hash冲突,且不支持范围查询、排序,只支持=、in。

二叉树

一颗相对平衡的有序二叉树,可进行插入、查找、删除。O(logn)

缺点:存在致命的倾斜性问题,如

果数据往大从小插入,或是由小从大插入 ,都会导致倾斜。即最大化查询。

红黑树

相对二叉树更加平衡,查询的次数也相对可以接受,但是红黑树自旋后还是会发生倾斜性的问题。

B-Tree

叶节点具有相同的深度,叶节点的指针为空;

所有索引元素不重复;

节点中的数据索引从左到右递增排列

B+Tree(B-Tree加强)

非叶子节点不存储data,只存储索引(冗余),可以放更多的索引

叶子节点包含所有索引字段

每个节点都有指定的degree,相邻节点靠指针关联(链表),值存在叶子节点上

 

引擎下实现

mysql索引时如何存储的: 引擎是表级别的,持久的,是一个文件,存储在磁盘上

MyISAM(非聚集)

不支持事务、也不支持外键,优势是访问速度快,对事务完整性没有 要求或者以select,insert为主的应用基本上可 以用这个引擎来创建表,支持FULLTEXT索引,并且只为CHAR、VARCHAR和TEXT列。

frm:创建表的文件

myd:表的数据文件

myi:表的索引文件,存的地址

索引查找: 以id为索引的B+tree(myi文件),得到id对应的物理地址(叶子结点上),然后再去myd文件查找对应的数据。以字符型,中文的为索引,存的就是ASCII,重复度很高不建议用索引(男女),磁盘IO还是会发生,浪费资源。

 

InnoDB(聚集)

该存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全。但是对比MyISAM引擎,写的处理效率会差一些,并

且会占用更多的磁盘空间以保留数据和索引。

InnoDB存储引擎的特点:支持自动增长列,支持外键约束

聚集索引 :插入的时候会按主键排序

frm:创建表的文件

ibd:索引+数据

索引查找:以id为索引的B+tree(myi文件),叶子节点存的是id+数据(如1,a)

以字符型,中文的(username)为索引,叶子节点存的是id;降低存储空间,减少索引创建

叶子结点每页默认是16k数据。

 

为什么建议InnoDB表必须建主键,并且推荐使用整型的自增主键?

答:mysql在建表时,会主动寻找某一个没有相同数据的列,没有则会创建一个列,相当于rowid,会浪费时间,而且在索引查找的时候,B+Tree存的是记录的ID,如果是rowid不利于查找。

自增主键,涉及了B+Tree数叶子结点的裂变,当叶子结点存不了数据时,会新开一个节点,这时候使用自增id,效率更高,如果用uuid等,还需要每次都去比较,而且uuid字符比较可能会消耗更多的时间。

为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)

答:非主键索引,比如二级索引,字符列name加的索引,叶子结点上key是name值,value是对应的记录ID,因为存的是ID,可以进行回表查询操作,更精确地查找记录,保证数据的一致性。而且不用像唯一索引一样去维护整个数据,可以节省内存空间。(没新增一个索引就多一个B+Tree的结构)

 

联合索引

多个列进行的组合索引,查询需符合最左前缀原则。

例:现有一个索引 a_b_c -->以下组合可用 : a,b,c ; a,b ; a 三种情况

 

底层数据结构:

也是B+Tree实现,不过非叶子结点存的是组合的值,如name、age,Alice 12, Bob 14,先对name进行排序,再对age进行排序。

认识Mysql索引

上一篇:Windows下使用zeppelin、Dockers搭建Flink学习环境


下一篇:阿里云发票识别功能评测