索引

定义：索引是用来快速检索出具有特定值的记录

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';
  

  ​ 聚集索引在性能上，不如非聚集索引。为什么这么说呢？聚集索引的方式，将数据和索引都存储在一个文件中，当数量越来越大时，文件读取速率也自然变慢，这就导致在性能上，不如非聚集索引。