先来看个问题

假设现在有100000条从0到10000且从大到小排列的整型数据，1条数据的大小假设(真的只是假设)是1KB,操作系统的每次I/O数据块(页)大小是8KB。如果现在我要查找其中 50001 这个数据值，有如下几个方式：

1. 最蠢的方式，遍历，每次遍历到一个值，就用这个值跟目标值做对比，如果不等于那么查找下一个。这样的话那么每次I/O是8条数据，目标数据在50001/8 约6600多次I/O 才能找到目标数据。
2. 二分查找，最好一次性将100000条数据全部读到内存，这样查找也是很快的。

但是即使二分查找很快，但这些数据也不能单单通过一次I/O全部进入内存，进行运算。

那么怎样在I/O块大小的限制下快速利用二分查找找到目标值呢？我们得引入新的数据结构，B+树正好可以解决上述I/O块大小的限制，解决限制不是说增大了限制范围，而是我们在此限制上改变了数据的存储结构，即在同等限制条件下，快速检索到目标数据，下面讲解下B+ Tree

image

上图中：

1. 图上蓝色的块为关键字，我们发现所有的关键字最终都会被包含在叶子节点当中。图上的黄色区块表示的是子树的指针域，比如根节点下的P2指向的就是28-65之间的索引。
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而B树的非终节点也包含需要查找的有效信息)

因此：数据 60 的 查找过程如下

1. I/O第一次：读入5、28、65数据块，在此同级别节点块上，60在28到65之间(其实是二分查找)，那走P2指针指向的子树。
2. I/O第二次：读入28、35、56数据块，在此同级别节点块上，60大于56，所以走P3指针指向的子树(上图中就是叶子节点)。
3. I/O第三次：读入叶子节点，在这个叶子节点中，使用二分查找算法找到目标值60。

预备知识

InnoDB中，各个数据页之间组成一个双向链表（页之间未必连续，所以是链表），而每个数据页内的记录又组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

image

概述

索引是在存储引擎中实现的，也就是说不通存储引擎，会使用不同的索引。

• MyISAM和InnoDB存储引擎：只支持BTREE索引，也就是说默认使用BTREE，不能够更换
• MEMORY/HEAP存储引擎：支持HASH和BTREE索引

索引优化也是mysql中的一种优化方式，mysql索引的四种类型：

• 单列索引（普通索引、主键索引、唯一索引——都只对一个字段建立索引）
• 组合索引
• 全文索引
• 空间索引（少用）

索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录

四种索引

• 普通索引

  纯粹只是为了查询更快，没有任何限制

  alter table table_name add index index_name ('字段名')
  

• 主键索引

  唯一索引中的一种，需要指定PRIMARY KEY，一表只有一个主键

  alert table table_name add primary key ('key name');
  
  create table 'student'(
      'stu_id' int(11) not null auto_increment,
      primary key('stu_id')
  )ENGINE=INNODB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8;
  

• 唯一索引

  索引列的值唯一，值可以为空（允许多个空值）

  create unique index UK_student_name on student(name);
  
  alter table table_name add unique index index_name ('key name');
  
  create table 'student'(
      'stu_id' int(11) not null auto_increment,
      'name' varchar(255) default null,
      primary key('stu_id'),
      unique key 'UK_student_name' ('name')
  )ENGINE=INNODB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8;
  
  建表后添加约束:
  alter table student add constraint uk_student_name unique (name);
  

• 组合索引

  在表中多个字段的组合上建立索引，使用组合索引需要遵循最左前缀集合（在查询条件中使用这些字段的左边字段），例如：由id、name和age3个字段构成的索引，索引行中就按id/name/age的顺序存放，索引可以索引下面字段组合(id，name，age)、(id，name)或者(id)。如果要查询的字段不构成索引最左面的前缀，那么就不会是用索引，比如，age或者（name，age）组合就不会使用索引查询

  创建组合索引应该把最频繁使用的字段放在最左边

• 全文索引（前缀索引）

  当索引的字符串列很大时，创建的索引也就变得很大，为了减小索引体积，提高索引的扫描速度，就用索引的前部分字串索引，这样索引占用的空间就会大大减少，并且索引的选择性也不会降低很多。而且是对BLOB和TEXT列进行索引，或者非常长的VARCHAR列，就必须使用前缀索引，因为MySQL不允许索引它们的全部长度。

  使用：
  列的前缀的长度选择很重要，又要节约索引空间，又要保证前缀索引的选择性要和索引全长度选择性接近。

  MyISAM支持全文索引，InnoDB在mysql5.6之后支持了全文索引，只能在CHAR,VARCHAR,TEXT类型字段上使用全文索引，全文索引就是在一堆文字中，通过其中的某个关键字等，就能找到该字段所属的记录行，比如有"你在吃饭，它在看电视" 通过“吃饭”，可能就可以找到该条记录。

  但是可能耗时间、耗空间

  alter table table_name add fulltext ('col_name');
  
  

  全文索引并不是和MyISAM一起诞生的，它的出现是为了解决WHERE name LIKE “%word%"这类针对文本的模糊查询效率较低的问题。

• 空间索引

  空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有四种，GEOMETRY、POINT、LINESTRING、POLYGON。在创建空间索引时，使用SPATIAL关键字。要求，引擎为MyISAM，创建空间索引的列，必须将其声明为NOT NULL。可能跟游戏开发有关。

mysql索引的两种结构

IndexType.jpg

• Hash索引

  MySQL中，只有Memory（Memory表只存在内存中，断电会消失，适用于临时表）存储引擎显示支持Hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。hsah索引把数据的索引以hash形式组织起来，因此当查找某一条记录的时候,速度非常快。当时因为是hash结构，每个键只对应一个值，而且是散列的方式分布。所以他只在“=”和“in”条件下高效，并不支持范围查找和排序等功能

  innodb会监控表上的索引使用情况，如果观察到建立哈希索引可以带来速度的提升，那就建立哈希索引，自 适应哈希索引通过缓冲池的B+树构造而来，因此建立的速度很快，不需要将整个表都建哈希索引，InnoDB 存储引擎会自动根据访问的频率和模式来为某些页建立哈希索引。自适应哈希索引不需要存储磁盘

• B+ Tree索引

  MYSQL、PGSQL、SQL-SERVER-ORACLE都离不开B-TREE索引，HASH索引，B-TREE可以做范围查找，基于叶子节点的查找适合于WHERE语句。MYSQL对WHERE A=XXXX特别做了优化，使用了HASH索引，HASH索引则适合于随机查找，无法或需要做SCAN时需要其他的方式。

  B+tree是mysql使用最频繁的一个索引数据结构，是Inodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+树在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以他更受用户的欢迎。毕竟不可能只对数据库进行单条记录的操作。

  带顺序访问指针——

  B+Tree所有索引数据都在叶子结点上，并且增加了顺序访问指针,每个叶子节点都有指向相邻叶子节点的指针。这样做是为了提高区间查询效率，例如查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

  减少磁盘I/O读取——

  用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

  实际实现B- Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

  B+ Tree根节点常驻内存

ps：

• 索引合并，使用多个单列索引组合搜索
• 覆盖索引，select的数据列只用从索引中就能够取得，不必读取数据行，换句话说查询列要被所建的索引覆盖

另一种分类方式（另一篇文章细讲）

InnoDB主键使用的是聚簇索引，MyISAM不管是主键索引，还是二级索引使用的都是非聚簇索引。

image

• 聚簇索引

  对于聚簇索引表来说（左图），表数据是和主键一起存储的，主键索引的叶结点存储行数据(包含了主键值)，二级索引的叶结点存储行的主键值。使用的是B+树作为索引的存储结构，非叶子节点存储索引关键字+页地址（可能有几层，因此需要存储往下面走的页的地址），叶子节点上的数据是主键与具体记录(数据内容)。

  要注意的是，在InnoDB中，由于在叶子节点也就是包含记录的页上，页内包含的记录也会按照索引列排序，这样是方便在页内可以进行二分查找；与此同时，带来的坏处是，如果此页已满，此时插入数据，可能导致需要分页的情况发生

• 非聚簇索引

  对于非聚簇索引表来说（右图），表数据和索引是分成两部分存储的，主键索引和二级索引存储上没有任何区别。使用的是B+树作为索引的存储结构，所有的节点都是索引，叶子节点存储的是索引+索引对应的记录的地址（类似指针）。

  非聚簇索引的页是按照时间顺序插入记录！也就是说一页里的内容是无序的

聚簇索引的优点:

1. 当你需要取出一定范围内的数据时，用聚簇索引也比用非聚簇索引好。
2. 当通过聚簇索引查找目标数据时理论上比非聚簇索引要快，因为非聚簇索引定位到对应主键时还要多一次目标记录寻址,即多一次I/O。

聚簇索引的缺点:

1. 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键（不懂！！！）。
2. 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
3. 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。二级索引的叶节点存储的是主键值，而不是行指针（非聚簇索引存储的是指针或者说是地址），这是为了减少当出现行移动或数据页分裂时二级索引的维护工作，但会让二级索引占用更多的空间。
4. 采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多，因为插入要保证主键不能重复，判断主键不能重复，采用的方式在不同的索引下面会有很大的性能差距，聚簇索引遍历所有的叶子节点，非聚簇索引也判断所有的叶子节点，但是聚簇索引的叶子节点除了带有主键还有记录值，记录的大小往往比主键要大的多。这样就会导致聚簇索引在判定新记录携带的主键是否重复时进行昂贵的I/O代价。

索引的扫描方式

• 紧凑扫描

  数据与索引不是放在一块的，索引中存放了指向对应数据行的指针，索引较小，所以比全表扫描快

• 松散扫描

  为了提高紧凑索引扫描效率，通过把索引排序和查找算法（B+trre），发现只需要和每个数据块的第一行键值匹配，就可以判断下一个数据块的位置或方向，因此有效数据就是每个数据块的第一行数据，如果把每个数据块的第一行数据创建索引，这样在这个新创建的索引上折半查找，数据定位速度将更快。这种索引扫描方式就称为松散索引扫描。

• 覆盖扫描

  包含所有满足查询需要的数据的索引称为覆盖索引，即利用索引返回select列表中的字段，而不必根据索引再次读取数据文件

一些要注意的

1. 唯一索引与唯一约束

   mysql中貌似唯一约束就是唯一索引，并没有什么不同，可能叫法不同，在sqlserver中区分还是挺明确的。

   博客中的一句话说的很在理，你为了做到数据不能有重复值，但是数据库怎么保证没有重复值呢？当然是在存储数据的时候查一遍，那么怎样查找快呢？ 当然是创建索引，所以，在创建唯一约束的时候就创建了唯一索引。这可能也是mysql的一个优化机制

2. MySQL只对<，<=，=，>，>=（!=不走索引），BETWEEN，IN，以及某些时候的LIKE才会使用索引（在以通配符%和_开头作查询时，MySQL不会使用索引）

3. 添加索引的时候，可以不写index

索引的代价

1. 空间耗费
2. 在使用DML语言对表格进行修改的时候，同时需要修改索引，降低效率
3. 如果该字段没有限制非空的话，存在插入NULL值的情况，此时，唯一索引并不起作用，也就是你可以插入n条该字段为null的数据。
4. 如果插入空字符串的话， 例如 ‘’ 、‘ ’
   不管中间是多少个空字符串在插入的时候都算作‘’，即，空串不论多长，只能插入一条。

在哪些字段上使用索引

• 频繁作为查询条件者
• 字段值更新不会太频繁者
• 字段值不会仅仅在几个确定的值上进行选择

选择索引的数据类型

MySQL支持很多数据类型，选择数据类型建立索引遵循一些规则：

• 越小的数据类型

  越小的数据类型通常在磁盘、内存和CPU缓存中都需要更少的空间，处理起来更快

• 简单的数据类型

  整型数据比起字符，处理开销更小，因为字符串的比较更复杂。

  在MySQL中，应该用内置的日期和时间数据类型，而不是用字符串来存储时间；

  用整型数据类型存储IP地址

• 尽量避免NULL

  含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值

选择主键类型

• 整型：通常是作为标识符的最好选择，因为可以更快的处理，而且可以设置为AUTO_INCREMENT。
• 字符串：尽量避免使用字符串作为标识符，它们消耗更好的空间，处理起来也较慢。而且，通常来说，字符串都是随机的，所以它们在索引中的位置也是随机的，这会导致页面分裂、随机访问磁盘，聚簇索引分裂（对于使用聚簇索引的存储引擎）。

索引的操作

查看

show index from 'table_name';

删除

alter table 'table_name' drop index 'index_name';

drop index index_name on table_name;

添加主键索引：指定主键即可

添加唯一索引、普通索引、复合索引、复合前缀索引（也可以复合单列索引，只要后面添加数字即可）

alter table 'table_name' add index index_name (column_name[, column_name[, column_name(10)]])