- 数据库    - 索引

数据库索引技术

详细介绍数据库索引的应用、原理及注意细节

Posted by chengweii on October 22, 2017

数据库索引

数据库索引是用于提高数据库表的数据访问速度的。数据库索引的特点：

  • 避免进行数据库全表的扫描，大多数情况，只需要扫描较少的索引页和数据页，而不是查询所有数据页。而且对于非聚集索引，有时不需要访问数据页即可得到数据。
  • 聚集索引可以避免数据插入操作，集中于表的最后一个数据页面。
  • 在某些情况下，索引可以避免排序操作。

聚集索引

聚集索引 聚集索引表的数据按照索引的顺序存储。对于聚集索引，叶子结点是存储了真实数据的数据行，不再有单独的数据页。
在一张表上只能创建一个聚集索引，因为真实数据的物理顺序只可能是一种。
如果一张表没有聚集索引，name它被称为“堆集”(Heap)。这样的表中的数据行没有特定的顺序，所有的新行将被添加到表的末尾位置。

Mysql InnoDB的数据基于聚集索引存储。在InnoDB表中，其聚集索引相当于整张表，而整张表也是聚集索引。
每张InnoDB表只能创建一个聚集索引，聚集索引可以由一列或多列组成。

InnoDB是聚集索引组织表，聚集索引由引擎自动选择，选择规则如下：主键索引>非NULL唯一索引>ROWID。

首先选择显式定义的主键索引做为聚集索引;如果没有，则选择第一个不允许NULL的唯一索引;还是没有的话，就采用InnoDB引擎内置的ROWID作为聚集索引。

查询

通过聚集索引进行查询时，会进行N次数据页查询。同时查询通常是由磁盘获取，但在访问频率较高时，缓存会保存高层索引，此时查询有可能是从缓存读取。

插入

对于聚集索引表，在插入数据时，首先根据索引找到对应的数据页，如果该数据页未满，则挪到已有记录并插入数据；如果数据页已满，则需要新增和拆分数据页。 一般情况下，此时首先检查该数据页的数据段是否已满，如果数据段已满则分配新段，创建数据页并插入数据，然后调整索引指针，这需要将相应的索引页读入内存并加锁，如果该表还有非聚集索引，则需要更新这些索引指向新的数据页。 然而在某些特殊情况下会进行一些特殊处理，如果插入的记录很大，为了提高效率，会分配两个数据页，一个用来存储新纪录，另一个则用来存储拆分出来的记录，通常数据库系统会将重复的记录存储于相同的数据页中。

删除

对于聚集索引表，在删除数据时，首先找到记录删除数据，然后检查对应数据页是否为空，如果为空则回收该数据页；检查完数据页后再检查所在数据段，如果为空则回收该数据段；最后更新索引页（删除数据对应索引、合并索引）。

索引合并：删除数据可能导致索引页中只有一条记录，该记录会被移至邻近的索引页，原索引页将被回收。

非聚集索引

非聚集索引 非聚集索引表的数据存储与索引顺序无关。对于非聚集索引，叶子结点包含索引字段值及指向数据页数据行的逻辑指针，该层紧邻数据页，其行数量与数据表行数量一致。

查询

通过非聚集索引查询时，会进行N-1次索引页的查询、1次数据页查询。同时查询通常是由磁盘获取，但在访问频率较高时，缓存会保存高层索引，此时查询有可能是从缓存读取。

插入

在插入数据时，如果表包含聚集索引，通过聚集索引查询插入位置并插入数据，同时更新非聚集索引；如果表不包含聚集索引，则插入到最末的数据页中，然后更新非聚集索引。

删除

删除数据时，首先找到记录删除数据，然后检查对应数据页是否为空，如果为空则回收该数据页；检查完数据页后再检查所在数据段，如果为空则回收该数据段；最后更新索引页（删除数据对应索引、合并索引）。

单列索引、复合索引

索引只包含一列的称为单列索引，而包含多列的索引称为复合索引，因为BTREE索引是顺序排列的，所以比较适合范围查询，但是在复合索引中，还应注意列数目、列的顺序以及前面范围查询的列对后边列的影响。

索引类型

普通索引(Normal)

最基本的索引，它没有任何限制。

//语法：CREATE INDEX index_name ON table(column(length));
CREATE INDEX idx_test ON test_table(title(4));

唯一索引(Unique)

唯一索引与普通索引类似，不同的是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。

//语法：CREATE UNIQUE INDEX indexName ON table(column(length));
CREATE UNIQUE INDEX idx_test ON test_table(title(4));

主键索引

主键索引是一种特殊的唯一索引，一个表只能有一个主键，不允许有空值。一般是在建表的时候同时创建主键索引：

CREATE TABLE `table` (
         `id` int(11) NOT NULL AUTO_INCREMENT ,
         `title` char(255) NOT NULL ,
         PRIMARY KEY (`id`)
     );

组合索引

组合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用组合索引时遵循最左前缀集合

// ALTER TABLE `table` ADD INDEX name_city_age (name,city,age); 
ALTER TABLE `table` ADD INDEX idx_test (name,city,age);

全文索引(Full Text)

全文索引主要用来查找文本中的关键字，而不是直接与索引中的值相比较。fulltext索引跟其它索引大不相同，它更像是一个搜索引擎，而不是简单的where语句的参数匹配。

CREATE TABLE `table` (
    `id` int(11) NOT NULL AUTO_INCREMENT ,
    `title` char(255) CHARACTER NOT NULL ,
    `content` text CHARACTER NULL ,
    PRIMARY KEY (`id`),
    FULLTEXT (content)
);

索引结构

BTREE

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。MySQL就普遍使用B+Tree实现其索引结构。以下为B+Tree的示意图： BTREE BTREE

HASH

简要说下，类似于数据结构中简单实现的HASH表（散列表）一样，当我们在mysql中用哈希索引时，也是对索引列计算一个散列值（类似md5、sha1、crc32），然后对这个散列值以顺序（默认升序）排列，同时记录该散列值对应数据表中某行的指针，当然这只是简略模拟图。 哈希索引的结构决定了它的特点： 1.hash索引只是hash值顺序排列，跟表数据没有关系，无法应用于order by； 2.hash索引是对它的所有列计算哈希值，因此在查询时，必须带上所有列，比如有(a, b)哈希索引，查询时必须 where a = 1 and b = 2，少任何一个不行； 3.hash索引只能用于比较查询 = 或 IN，其他范围查询无效，本质还是因不存储表数据； 4.一旦出现碰撞，hash索引必须遍历所有的hash值，将地址所指向数据一一比较，直到找到所有符合条件的行。

BITMAP(Oracle)

如果对于性别列（男或女）等，则使用位图索引会比较好，因为它对空间的占用非常少（因为都是用bit位来表示表里的数据行），从而在扫描索引的时候，扫描的索引块的个数也比较少。
如果索引列上不同值的个数比较少的时候
注意：如果被索引的列经常被更新的话，则不适合使用位图索引。因为在更新索引条目的过程中，会锁定位图索引里多个索引条目。也就是同时只能有一个用户能够更新表T，从而降低了并发性。位图索引比较适合用在数据仓库系统里，不适合用在OLTP系统里。

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图： 主索引 该表共有三列，Col1为主键。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

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

如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示： 辅助索引 同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。第一个重大区别是InnoDB的数据文件本身就是索引文件。

从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。 主索引 从图中可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，在Col3定义上的一个辅助索引： 辅助索引 这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

索引优化

MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。
在了解具体优化策略之前，首先要理解索引使用的一些原则，包括：最左前缀原则、索引选择性。

最左前缀原则

高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。 以employees.titles表为例，该表上有一个主索引<emp_no, title, from_date>： employees.titles索引

情况一：全列匹配

全列匹配 当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。需要注意的是，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，所以将where中的条件顺序颠倒，效果也是一样的： 全列匹配自动优化

情况二：最左前缀匹配

最左前缀匹配 当查询条件精确匹配索引的左边连续一个或几个列时，如或<emp_no, title>，所以可以被用到，但是只能用到一部分，即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引，但是key_len为4，说明只用到了索引的第一列前缀。

情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供

最左前缀匹配部分匹配 此时索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date（这里由于emp_no唯一，所以不存在扫描）。
如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引<emp_no, from_date>，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为“隔离列”的优化方法，将emp_no与from_date之间的“坑”填上。
首先我们看下title一共有几种不同的值： 最左前缀匹配部分匹配补坑 只有7种。在这种成为“坑”的列值比较少的情况下，可以考虑用“IN”来填补这个“坑”从而形成最左前缀： 最左前缀匹配部分匹配补坑 这次key_len为59，说明索引被用全了，但是从type和rows看出IN实际上执行了一个range查询，这里检查了7个key。看下两种查询的性能比较： 最左前缀匹配部分匹配性能对比 “填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据，则后者性能优势会更加明显。当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。

情况四：查询条件没有指定索引第一列

查询条件没有指定索引第一列 由于不是最左前缀，索引这样的查询显然用不到索引。

情况五：匹配某列的前缀字符串

匹配某列的前缀字符串 此时可以用到索引，如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀。

情况六：范围查询

范围查询 范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。 范围查询 可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方，那就是仅用explain可能无法区分范围索引和多值匹配，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询： 范围查询 看起来是用了两个范围查询，但作用于emp_no上的“BETWEEN”实际上相当于“IN”，也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配，否则会对MySQL的行为产生困惑。

情况七：查询条件中含有函数或表达式

很不幸，如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引（虽然某些在数学意义上可以使用）。例如： 查询条件中含有函数或表达式 虽然这个查询和情况五中功能相同，但是由于使用了函数left，则无法为title列应用索引，而情况五中用LIKE则可以。再如： 查询条件中含有函数或表达式 显然这个查询等价于查询emp_no为10001的函数，但是由于查询条件是一个表达式，MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度，因此在写查询语句时尽量避免表达式出现在查询中，而是先手工私下代数运算，转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。

  • 第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。
  • 另一种不建议建索引的情况是索引的选择性较低。

    所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
    Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。例如，上文用到的employees.titles表，如果title字段经常被单独查询，是否需要建索引，我们看一下它的选择性：

索引选择性与前缀索引

title的选择性不足0.0001（精确值为0.00001579），所以实在没有什么必要为其单独建索引。有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。可以看到employees表只有一个索引，那么如果我们想按名字搜索一个人，就只能全表扫描了：

索引选择性与前缀索引

如果频繁按名字搜索员工，这样显然效率很低，因此我们可以考虑建索引。有两种选择，建first_name或first_name,last_name，看下两个索引的选择性：

索引选择性与前缀索引

显然first_name选择性太低，first_name,last_name选择性很好，但是first_name和last_name加起来长度为30，有没有兼顾长度和选择性的办法？可以考虑用first_name和last_name的前几个字符建立索引，例如<first_name, left(last_name, 3)>，看看其选择性：

索引选择性与前缀索引

选择性还不错，但离0.9313还是有点距离，那么把last_name前缀加到4：

索引选择性与前缀索引

这时选择性已经很理想了，而这个索引的长度只有18，比first_name, last_name短了接近一半，我们把这个前缀索引建上：

索引选择性与前缀索引

此时再执行一遍按名字查询，比较分析一下与建索引前的结果：

索引选择性与前缀索引

性能的提升是显著的，查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。

接下来我们从结构优化和查询优化两方面来了解一些具体的优化手段：

结构优化

  • 在InnoDB中不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
  • 在InnoDB中不建议用非单调的字段作为主键，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
  • 在InnoDB中，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
  • 为了兼顾索引的大小和查询速度，可以通过前缀索引（截取字段左边部分内容构建索引）的方式优化索引。
  • 尽量使用数字型字段，若只含数值信息的字段尽量不要设计为字符型，这会降低查询和连接的性能，并会增加存储开销。这是因为引擎在处理查询和连接时会逐个比较字符串中每一个字符，而对于数字型而言只需要比较一次就够了。

    查询优化

  • Where、Group by、Order by时使用的字段要尽可能遵循最左前缀原则，否则无法使用到索引。
  • 对查询进行优化，应尽量避免全表扫描，首先应考虑在 Where、Group by、Order by 涉及的列上建立索引。
  • 尽量使用覆盖索引（只访问索引的查询(查询的列与索引的列一致)），尽量避免select * 。
  • 优化关联查询
    • 关联查询的表仅需在外键列所在的子表建立索引即可，关联主表无需创建，否则反而会增加负担。
    • 确保Group by和Order by中的表达式只涉及到一个表的列，这样才有可能使用索引来优化这个过程。
  • 尽量避免查询无法使用索引的情况：
    • Mysql5.7之前查询条件中含有函数或表达式时无法使用索引，故查询条件中尽量避免出现表达式，而是先手动运算，转换为无表达式的查询语句。
    • 字段值为Null时无法使用索引，故要索引的字段在创建时要尽可能设置默认值。
    • 在 where 子句中使用!=或<>操作符时字段无法使用索引。
    • like以通配符(%)开头的字段查询无法使用索引，故查询应尽量避免此种情况。
    • 在 where 子句中使用or时，必须or表达式中的字段都建有索引，否则无法使用索引，若要使用索引可以通过union替代or。

参考文献

MySQL索引背后的数据结构及算法原理
数据库索引详解
MySQL的聚集索引和非聚集索引
MySQL表为什么必须有主键 – 聚集索引的简单介绍
聚集索引、非聚集索引、聚集索引组织表、堆组织表、Mysql/PostgreSQL对比、联合主键/自增长、InnoDB/MyISAM（引擎方面另开一篇）
聚集索引和非聚集索引（整理）
Mysql技术内幕——InnoDB存储引擎
oracle索引原理（b-tree,bitmap,聚集，非聚集索引）
mysql关于or的索引问题

CATALOG
    FEATURED TAGS
       - java 分布式 数据库 多线程 - 实践 Nginx 应用
    FRIENDS