数据库之索引详解

文章目录

• 一、索引的概念
• 1、什么是索引？
• 2、为什么要用索引？
• 二、B-树、B+树、和红黑树简介
• 1、B-树简介
• 2、B+树简介
• 3、红黑树简介
• 三、为什么用B-/+树作为索引
• 1、主存和磁盘存取
• 2、B-/+Tree索引的性能分析
• 3、B+Tree的性质
• （1）索引字段要尽量的小
• （2）索引的最左匹配特性（即从左往右匹配）
• 四、聚集索引和非聚集索引
• 1、聚集索引
• 2、非聚集索引
• 3、聚集索引和非聚集索引的区别
• （1）存储特点的区别：
• （2）更新表数据的区别：
• 4、何时使用聚集索引或非聚集索引？
• 五、MySQL索引实现
• 1、MyISAM索引实现
• 2、InnoDB索引实现
• 六、索引的类别
• 1、普通索引/单列索引
• 2、唯一索引
• 3、联合索引
• 4、全文索引
• 5、空间索引
• 6、索引的增删改查
• 七、索引的优缺点及注意事项
• 1、使用索引的优点
• 2、使用索引的缺点
• 3、创建索引的几大原则

一、索引的概念

1、什么是索引？

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构（类似书籍的目录）。提取句子主干，就可以得到索引的本质：索引是一种数据结构。

2、为什么要用索引？

一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。

索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级。索引相当于字典的音序表，如果要查某个字，如果不使用音序表，则需要从几百页中逐页去查。

【注意】：

• 索引需要占用磁盘空间，因此在创建索引时要考虑到磁盘空间是否足够。
• 创建索引时需要对表加锁，因此实际操作中需要在业务空闲期间进行。

二、B-树、B+树、和红黑树简介

1、B-树简介

• 每个节点最多有m个孩子。
• 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
• 若根节点不是叶子节点，则至少有2个孩子。
• 所有叶子节点都在同一层，且不包含其它关键字信息。
• 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn） 。
• 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1 。
• ki(i=1,…n)为关键字，且关键字升序排序。
• Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)。

【模拟查找关键字29的过程】：

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6. 在磁盘块8中的关键字列表中找到关键字29。

2、B+树简介

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
  从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

【B+Tree相对于B-Tree有几点不同】：

• 非叶子节点只存储键值信息。
• 所有叶子节点之间都有一个链指针。
• 数据记录都存放在叶子节点中。

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

3、红黑树简介

• 每个节点非红即黑；
• 根节点是黑的；
• 每个叶节点(叶节点即树尾端NUL指针或NULL节点)都是黑的；
• 如果一个节点是红的,那么它的两儿子都是黑的；
• 对于任意节点而言,其到叶子点树NIL指针的每条路径都包含相同数目的黑节点。

三、为什么用B-/+树作为索引

索引的本质：通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。

在上一节中可以看出，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

1、主存和磁盘存取

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

2、B-/+Tree索引的性能分析

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(log_dN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

而红黑树结构，h明显要深得多。由于逻辑上很近的结点（父子结点）物理上可能离得很远，无法利用局部性原理。所以即使红黑树的I/O渐进复杂度为O(h)=O(log_2N)，但是查找效率明显比B-Tree差得多。

3、B+Tree的性质

（1）索引字段要尽量的小

通过上面的分析，我们知道IO次数取决于b+树的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

（2）索引的最左匹配特性（即从左往右匹配）

当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+树是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。

四、聚集索引和非聚集索引

mysql中普遍使用B+Tree做索引，但在实现上又根据聚集索引和非聚集索引而不同。

1、聚集索引

所谓聚集索引，就是指主索引文件和数据文件为同一份文件，聚集索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身，key为主键，如果是一般索引的话，data便会指向对应的主索引，如下图所示：

  在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

2、非聚集索引

非聚集索引就是指B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址。主索引和辅助索引没啥区别，只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中，如下图：

  非聚集索引比聚集索引多了一次读取数据的IO操作，所以查找性能上会差。

3、聚集索引和非聚集索引的区别

（1）存储特点的区别：

• 聚集索引按索引顺序来存储，索引项顺序与表中记录的物理顺序一致，叶子节点即存储了真实数据行，不再有另外的单独数据页，一张表上最多只有一个聚集索引。
• 非聚集索引表的存储顺序与索引顺序无关，仅仅索引项的逻辑上是连续的，叶子节点存储了索引字段值以及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。

（2）更新表数据的区别：

• 插入数据：非聚集索引的表，表中数据行没特定顺序，新行皆被添加到表的末尾；聚集索引的表，先根据索引找到对应的数据页，挪动已有记录为新数据腾出空间后插入，若数据页已满，则拆分数据页，调整索引指针(若表中有非聚集索引，则更新索引指向新的数据页)。
• 删除数据：非聚集索引的表，直接删除(留下内存空洞)；聚集索引的表，删除行将导致其下的数据行向上移动以填补空白，若删除的行为数据页最后一行，则回收该数据页，相应索引页中记录也被删除。

这就是为什么主键上创建非聚集索引比主键上创建聚集索引在插入数据和删除数据时要快的真正原因。

【Note】：
  聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个。

4、何时使用聚集索引或非聚集索引？

五、MySQL索引实现

1、MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶子结点的data域存放的是数据记录的地址。下面是MyISAM索引的原理图：

  在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

2、InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

【第一个】重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

可以看到叶子结点包含了完整的数据记录。这种索引就是聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有）。【第二个】与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

六、索引的类别

1、普通索引/单列索引

CREATE TABLE t_user(
    `id` int primary key auto_increment,
    `username` varchar(20),
    INDEX(username)
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

2、唯一索引

// 索引列的值必须唯一，但允许有空值(和主键不同之处)，若是联合索引，则列值得组合必须唯一。
// 主键是一种特殊的唯一索引，不允许有空值。
CREATE TABLE t_user2(
    `id` int primary key auto_increment,
    `username` varchar(20),
    UNIQUE INDEX(username)
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

3、联合索引

// 索引包含多个字段但只有一个名称（最左匹配/前缀）
CREATE TABLE t_user3(
    `id` int primary key auto_increment,
    `username` varchar(20),
    INDEX(id, username)
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

4、全文索引

// 1、对于较大的数据集，将数据输入一个没有FULLTEXT索引的表中，然后创建索引，
// 其速度比把数据输入现有FULLTEXT索引的速度更为快。
///2、生成全文索引是一个非常耗时且非常耗硬盘空间的做法。
// 3、全文索引创建速度慢，而且对有全文索引的各种数据修改操作也慢。
CREATE TABLE t_user4(
    `id` int primary key auto_increment,
    `username` varchar(20),
    FULLTEXT INDEX(username)
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

5、空间索引

了解就好，几乎不用

6、索引的增删改查

/**** 1、在已有的数据表上创建索引 ****/

CREATE INDEX index_username ON t_user(username);

CREATE UNIQUE INDEX index_username ON t_user(username);

CREATE INDEX index_username ON t_user(id, username);

/**** 2、修改数据表结构添加索引 ****/

ALTER TABLE t_user ADD INDEX index_username(username);

ALTER TABLE t_user ADD UNIQUE INDEX index_username(username);

ALTER TABLE t_user ADD INDEX index_username(id, username);

/**** 3、删除索引 ****/

DROP INDEX index_username ON t_user;

七、索引的优缺点及注意事项

1、使用索引的优点

• 可以通过建立唯一索引或者主键索引,保证数据库表中每一行数据的唯一性。
• 建立索引可以大大提高检索的数据,以及减少表的检索行数。
• 在表连接的连接条件可以加速表与表直接的相连。
• 在分组和排序字句进行数据检索，可以减少查询时间中分组和排序时所消耗的时间(数据库的记录会重新排序)。
• 建立索引，在查询中使用索引可以提高性能。

2、使用索引的缺点

• 在创建索引和维护索引会耗费时间,随着数据量的增加而增加。
• 索引文件会占用物理空间,除了数据表需要占用物理空间之外,每一个索引还会占用一定的物理空间。
• 当对表的数据进行 INSERT,UPDATE,DELETE 的时候,索引也要动态的维护,这样就会降低数据的维护速度,(建立索引会占用磁盘空间的索引文件。一般情况这个问题不太严重，但如果你在一个大表上创建了多种组合索引，索引文件的会膨胀很快)。

3、创建索引的几大原则

• 最左前缀匹配原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like ‘%…’)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，若建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
• =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会优化成索引可识别的形式。
• 尽量选择区分度高(cardinality越大越好)的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，一般需要join的字段都要求是0.1以上，当然，使用场景不同，该值也难以确定。查询中很少使用到的列不应该创建索引，如果建立了索引然而还会降低mysql的性能和增大了空间需求。很少数据的列也不应该建立索引。
• 索引列不能是表达式的一部分或mysql函数的参数，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，因为b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，成本太大，故不能走索引，所以语句应写成create_time = unix_timestamp(’2014-05-29’) 。
• 尽量的扩展索引，不要新建索引，比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。
• 定义为text和image和bit数据类型的列不应该增加索引。
• 当表的修改(UPDATE,INSERT,DELETE)操作远远大于检索(SELECT)操作时不应该创建索引，这两个操作是互斥的关系。