• 索引的使用方法
• 索引的数据结构
• 不同存储引擎中的索引实现方式

MySQL数据库表的访问方式又两种：顺序访问、索引访问。
1、顺序访问：
直接进行全表扫描，根据条件逐行记录判断，指导找到相应结果为止。面对当前互联时代，数据量都是成百上千万的存在，这样的访问方式将会及其缓慢，不仅消耗资源还大大影响了效率。基本不会使用此方式。
2、索引访问：
为了解决大数据量情况下也能快速访问，就必须采用索引的方式。索引访问是通过遍历索引来直接访问表中记录行的方式（前提是在该列上有创建索引）。

一、MySQL数据库索引的使用

1、创建索引的几种方式：

• 创建表的时候同时创建索引：

CREATE TABLE table_name(          # table_name：表名
id INT NOT NULL PRIMARY KEY,      # PRIMARY KEY MySQL创建表之后会默认创建一个主键索引   
user_name VARCHAR(16) NOT NULL,  
INDEX idx_user_name (user_name(16))  # index_name 索引名称，user_name索引列，（16）长度，如果字段类型是BLOB或TEXT必须制定索引列长度，如果字段类型是CHAR或者VARCHAR可忽略指定长度  
);

• 直接创建索引

CREATE UNIQUE INDEX u_idx_id ON table_name(id);   # 创建唯一索引，一般用于主键，或者其他不能重复的常用查询字段。
CREATE INDEX index_name ON table_name(user_name); # 普通索引 user_name->表字段名

• 修改表结构的方式创建索引

ALTER TABLE table_name ADD UINDEX u_idx_id (id);                # 创建唯一索引
ALTER TABLE table_name ADD INDEX idx_user_name (user_name);     # 创建普通索引

2、删除索引

ALTER TABLE table_name DROP INDEX u_idx_id;    # 通过ALTER命令删除索引 table_name：表名，u_idx_id：索引名
DROP INDEX idx_user_name ON table_name;        # 通过DROP命令直接删除索引 idx_user_name：索引名，table_name：表名

3、查看索引

SHOW INDEX FROM table_name; #table_name：表名

二、MySQL数据库索引相关数据结构

二叉树、红黑树、B-Tree、B+Tree、Hash

1、为什么二叉树和红黑树不适合作为索引的数据结构？

• 二叉树不适合的原因：
  当某表的索引列为依次递增序列，如此的话，二叉树将会变成一个链表形式，不利于快速查找，因此二叉树不适合作为索引的数据结构。 在查找的过程中会多次进行磁盘I/O，将会影响系统性能、查询速度较慢。
• 红黑树不适合的原因：
  红黑树是一个平衡二叉树，在插入数据的时候，为了保持平衡二叉树的特性会发生自旋，相比二叉树来效率稍微高一些。
  不适合作为索引的主要原因是当数据量上百万之后，表的记录越多树的高度越高，树的高度不可控，也会使得磁盘I/O次数增多，也是相当耗费资源，影响系统性能。

2、B-Tree作为索引：

• 在红黑树上的基础上进行的改造，让每个节点可以横向存储多个元素，从而使得树的高度降低，减少的磁盘的I/O次数，从而提高性能，这也就是B-Tree的数据结构。
• B-Tree特点：
  1.叶子节点具有相同的深度，叶子节点的指针为空，叶子节点之间没有指针连接；
  2.所有索引元素不重复；
  3.节点中的数据索引从左至右依次递增。

• 如图下结构：

  
  B-Tree结构.png

其中，data可能存储的是当前索引列所属行的其他字段所有数据，当表字段较多，则data占用空间就会变大，当前大节点所能存储的索引总个数就会变少，从而当表数据量过大的时候树的高度也会变得不可控。（MySQL对大节点的默认大小是16K）

• 查看MySQL文件页大小的的SQL语句：

SHOW GLOBAL STATUS LIKE 'Innodb_page_size'; # 可修改，建议不要修改

• B-Tree作为索引存在的弊端：
  1.如果不是按照索引的最左列开始查找，则无法使用索引。
  2.不能跳过索引中的列
  3.如果查询中有某列的范围查询，则其右边所有列都无法使用索引优化查询。

3、B+Tree

MySQL数据库索引真正的数据结构是采用B+Tree实现的（B-Tree的变种）。

• B+Tree特点：
  1.非叶子节点不存储data，只存储索引（冗余）；
  2.叶子节点包含所有索引字段；
  3.叶子节点从左至右依次递增，叶子节点采用指针连接，提高区间访问的性能（模糊查询）。

• 结构如下图（高度为3）：

  
  B+Tree结构.png
• 计算MySQL的索引能存储多多少个元素：
  为减少磁盘I/O，大节点不能存储更多的索引。
  1).第一层（根节点）：MySQL表主键一般用bigint（占用磁盘空间8B），指针占用6B，此时一个索引元素（默认指针和索引是成对出现的）占用空间为14B，大节点的默认大小为16K。如此，计算一个大节点可以存储的索引元素个数为：16K / (8B + 6B) ≈ 1170个索引
  2).第二层（非叶子节点）：根据第一层可知，第二层应该存在1170大节点， 每个节点都存在1170个索引元素。
  3).第三层（叶子节点）：存在1170 * 1170个大节点，假设data和小节点总共占用1K，则一个叶子节点可以存在16个索引元素。
  综上，高度为3的B+Tree总共存储元素个数应该为：1170 * 1170 * 16个索引元素（大概2000万+）。
• 优点：
  1.B+Tree的高度远小于B-Tree（原因：B+Tree的非叶子节点不存储data，只存储索引，每个节点的大小固定，所以B+Tree的节点可以存储更多的索引。）。
  2.磁盘I/O次数极少，一般需要2次磁盘I/O（根节点存在于内存）。
  3.MySQL底层对B+Tree树叶子节点的指针做了优化，改为了双向指针。 叶子节点的指针就是为了便于范围查询，提高范围查询的效率，避免多次遍历B+Tree。

4、Hash表作为索引

Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的I/O访问，所以Hash索引的查询效率要远高于B-Tree索引。
之所以在使用中不采用Hash索引的主要原因是Hash索引不支持范围查询、不支持数据排序操作。也有可能发生Hash碰撞，但发生碰撞的概率极小。如果对某表的操作操作99%
都是等值查询则可以考虑使用Hash索引，否则不建议采用此索引。

三、MySQL数据库存储引擎索引实现

1、MyISAM存储引擎(非聚簇索引)

• MyISAM将数据文件和索引文件分开存储
• 主键索引和非主键索引结构相似
• 建表语句

CREATE TABLE table_myisam (           # table_myisam:表名称 
  id BIGINT(11) NOT NULL,
  user_id VARCHAR(16) NOT NULL,
  user_name VARCHAR(16) NOT NULL,
) ENGINE=MYISAM DEFAULT CHARSET=utf8  # EGINE=MYISAM 指定表的存储引擎

• 该表对应文件结构（windows文件目录在MySQL安装目录下的Data目录下，Linux目录默认在/var/lib/mysql/目录下）：

  
  MyISAM存储引擎的表对应的文件结构.png

• 索引结构：

  
  MyISAM索引结构.png

SQL查询过程：

SQL语句：

SELECT * FROM table_myisam WHERE id = 49;

查询过程：
通过B+Tree索引找到49所在的节点，将该节点数据写入内存，根据该节点data的信息直接去取数据文件的记录，再将结果写入内存。

2、InnoDB存储引擎(聚簇索引)

• 表数据文件本身就是按照B+Tree组织的一个索引结构文件

• 聚簇索引的叶子节点包含了完整的数据记录

• 主键索引和辅助索引的主要区别：
  1.主键索引：叶子节点的data存储该记录其他所有字段。
  2.辅助索引（非主键索引）：叶子节点的data存储该记录的主键。

• 建表语句

CREATE TABLE table_innodb (
  id BIGINT(11) PRIMARY KEY NOT NULL AUTO_INCREMENT,    # PRIMARY KEY:主键，AUTO_INCREMENT:自增
  user_id VARCHAR(16) NOT NULL,
  user_name VARCHAR(16) NOT NULL
) ENGINE=INNODB DEFAULT CHARSET=utf8;                   # ENGINE=INNODB：设定存储引擎为InnoDB

• 对应文件结构（文件目录同上所述MyISAM存储引擎的文件目录）：

  
  InnoDB存储引擎的表对应的文件结构.png

• 索引结构
  1.主键索引：

  
  InnoDB存储引擎主键索引结构.png
  

  2.辅助索引（非主键索引）：

  
  InnoDB存储引擎非主键索引结构.png

面试题：

• Q : 聚簇（聚集）索引和非聚簇（稀疏、非聚集）索引的概念？
  A : 聚簇索引就是将索引和数据记录存放在一起，非聚簇索引就是索引和数据记录是分开存储的。因此，MyISAM存储引擎的索引就是非聚簇索引，InnoDB存储引擎的索引就是聚簇索引。
• Q:为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
  A:
  1.必须有主键？ InnoDB的表数据就是按照B+Tree形式存储，所以必须要有主键并且默认有主键索引，MySQL的InnoDB存储引擎底层就是如此设计的。（没有明确指定主键的建表语句，MySQL底层会自动建一列字段(rowid)为主键，数据每插入一行rowid都会生成一个唯一的整型值）。
  2.整型主键？假设主键采用UUID的存储方式，MySQL会将UUID进行编码计算（逐个比较每个字符的ASCII码进行比较大小）得到一个值进行大小比较建立B+Tree索引数据文件。并且UUID占用磁盘空间较大，所以也不适合作为主键。
  3.自增？如果是整型自增的话，按照索引结构一般来insert数据说都是往后面添加元素，不需要过多的判断大小，改变数据指针指向。如果不是自增，会改变树的结构，不容易维护，影响系统性能。
• Q：为什么非主键索引结构叶子节点存储的是主键值？
  A:为保障数据一致性（如果一个表既存在主键索引也存在非主键索引，在insert之前需要先维护需要维护好索引结构，再讲数据写入表中，则意味着insert就可能出现类似分布式事务的问题，此时需要同时维护两个索引的数据，并且要保持一致之后才能完成真正的插入操作，不仅维护量大，而且会牵扯性能问题），并且可以节省存储空间（非主键索引的data只需要存储主键值，大大节省了存储空间）。

3、联合索引

• 创建联合索引：

# table_innodb : 表名， s_index：索引名， user_id、user_name：字段名
ALTER TABLE table_innodb ADD INDEX s_index (user_id, user_name, birth_date);    # 通过修改表结构的方式创建联合索引
CREATE INDEX s_index ON table_innodb (user_id, user_name, birth_date);          # 直接创建联合索引

• 底层存储结构：

  
  联合索引.png
• 解释：
  根据如上联合索引SQL建立所得的联合索引树结构图大致如上，在实际比较过程中遵循最左匹配原则，先比较user_id，从左至右依次递增；当user_id结果相同是再比较user_name，根据user_name的ASCII码值从左至右依次递增；当user_name结果也相同的时候，再比较birth_date。如此方式建立出树结构。
• 实际工作之中建议采用联合索引的方式，可以节省空间。
• 联合索引就是将多个字段存储到同一个节点之上。
• 联合索引排序顺序根据建立索引时候的字段顺序从左至右一次比较顺序

不妥之处还请指正...