定义:索引是用来快速检索出具有特定值的记录
MySQL官方定义:索引(index)是帮助MySQL高效获取数据的数据结构
快速检索数据结构:Hash算法、二叉树、红黑树、B Tree、B+Tree
-
Hash:时间复杂度O(1)
- 不足:
- 无法支持范围查询;
- 不支持排序
- 不足:
-
二叉树(不平衡):
- 不足:
- 虽然支持范围查询、但根据我们插入的顺序导致二叉树极端不平衡
- 不足:
-
红黑树:解决了二叉树不平衡的问题
- 不足:
- 相对于二叉树减少了右倾现象,没有从根本上解决倾斜问题
- 不足:
-
B+Tree:真实数据存在于叶子节点;非叶子节点不存储真实的数据,只存储指引搜索方向的数据项。B+Tree在树形结构的基础上,实现了横向的拓展,从根本上上解决了二叉树不平横的问题。
MySQL引擎索引分类
-
MyISAM(非聚集索引):
MyISAM是MySQL的默认数据库引擎(5.5版本以前),由早期的ISAM(Indexed Sequential Assess Method【有索引的顺序访问方法】)所改良,索然性能极佳,但却不支持事务
-
InnoDB(聚集索引):
InnoDB,是MySQL的数据库引擎之一,为MySQL AB发布binary的标准之一。InnoDB有Innobase Oy公司所开发,2006年5月时由甲骨文公司并购。与传统的ISAM与MyISAM相比,InnoDB的最大特色就是支持了ACID兼容的事务功能。类似于PostgreSQL。目前InnoDB采用双轨制授权,一是GPL授权,另一是专有软件授权。
非聚集索引与聚集索引的区别
-
非聚集索引:
非聚集索引,数据机构上采用B+Tree,只有叶子节点存储数据,且数据存储的是对应数据在磁盘中的地址,通过地址从而找到对应的数据。当使用MyISM作为存储引擎时,每个表会生成三种文件,其中frm为表定义结果存储文件,使用InnoDB时,也会存在该文件。而MYI文件为该表的索引文件,MYD为该表数据存储文件。
举例:
select * from table where id = 15;
当执行上方该sql时,数据库回去该表的MYI文件中查找,根据索引树,找到对应id为15的数据的存储地址为0x07,再到对应的MYD文件中,找到对应0x07地址存储的数据,完成一次查找。
-
聚集索引:
聚集索引与非聚集索引相似,其区别在于表的表数据和索引数据均存在IDB文件中。
在IDB文件的叶子节点中,存储的不是数据的存储地址,而是对应索引相对应的完整数据。如下右图所示,当查找id为15的数据时,即可找到对应的数据。
此外,当表中存在其他类型唯一索引时,MySQL也会为其生成索引树,但其叶子节点存储的数据为对应数据记录的ID。以上图为例,假设现存在一表,ID为主键,USER_NAME为唯一索引。当执行下方SQL时,数据库会先在辅助索引树中,查的对应的叶子节点数据(即为ID),再去主索引树中,查找获取对应的全部数据。select * from table where user_name = 'Jim';
聚集索引在性能上,不如非聚集索引。为什么这么说呢?聚集索引的方式,将数据和索引都存储在一个文件中,当数量越来越大时,文件读取速率也自然变慢,这就导致在性能上,不如非聚集索引。