《经典面试系列》- 索引

0、开胃菜：如何设计一个关系型数据库？

　

如上图，开发一个数据库，我们最主要讲数据库分成两个模块（存储模块、程序实例模块）。

  1. 存储模块：该模块类似于文件系统，将数据持久化到存储设备当中，如存入磁盘（机械硬盘、固态硬盘）或者磁盘阵列矩阵中。
  2. 程序实例：但是光有存储是不够的，我们还需要有程序实例模块来对存储进行逻辑上的管理。主要包括以下：
    • 将数据逻辑关系转换成物理存储关系的就存储管理模块。我们需要对数据格式、文件风格进行统一管理，即把物理数据通过逻辑的形式给组织、表示出来，这里就用到我们的就存储管理。

    • 优化执行效率的缓存机制模块。我们为了提高数据库的效率，会将数据加载到缓存中，这样我们在读取的时候就可以直接从缓存中返回。注意，缓存不宜过大，且算法里必须要有淘汰机制，以淘汰掉一些后面不常用的数据。 

    • 将SQL解析的SQL解析模块。我们还需要提供一个给外界指令来操作数据库功能，即可读的SQL语言。这是时候我们的SQL解析模块，就会将SQ　　L编译、解析成机器可识别的指令。这个时候，为了进一步提升SQL执行效率，我们依旧将SQL放到缓存里，编译好的SQL，我们在下次就可以直接执行。

    • 记录SQL操作的日志管理模块。我们的SQL操作需要记录下来，方便我们做主从同步、灾难恢复等。

    • 进行多用户划分的权限划分模块。数据库应具备有对用户私密管理的功能，实现权限管理、划分。

    • 异常、灾难恢复管理的容灾机制。在设计数据库时，不光考虑正常情况，还要考虑异常、灾难。我们在发生灾难时，对数据进行恢复，恢复到什么程度，这些都是有容灾机制进行管理。

    • 优化数据库查询效率的索引管理模块。

    • 使得数据库支持并发操作的锁管理模块。

1．为什么要用索引？

　　我们先说全表扫描：数据库存储的最小单位是块/页，是有多行记录组成的。（整个表就是多个块/页）我们把这些块或页加载进缓存，然后对每个块/页去轮询，找到目标并返回。（适用于数据比较小的表）

　　索引灵感来自字典，查字典可以通过部首、拼音快速查找，查数据可以通过逐渐、唯一键以及普通键（我们常说的关键字）进行快速查找。此外，我们还要将这些关键字以一种好的形式组织起来，即索引的数据结构。

　　使用索引，可以避免全表扫描，提高我们的查询效率。　　

　　例如有如下一张user表：主键id，姓名name，年龄age；表中有十万条数据;

　　现在，要从表中查询出姓名为＂zhagnSan＂的用户信息；SELECT * FROM user WHERE name =＇zhagnSan＇；

　　如果没有创建索引，数据库在执行该语句后，会进行全表扫描，即是数据库会遍历整张表，对每一行都要检查其字段name的值是否等于"zhagnSan"。因为我们要查询所有名字为＂zhagnSan＂的用户，当数据库查找到第一条数据时，它并不会停止扫描，而是继续查找，因为还可能有其他的用户也叫＂zhagnSan＂。这就意味着，表中的十万条数据，每一条数据库都要扫描一遍，这就是＂全表扫描＂。

2．什么是索引

　　索引就是数据结构。进一步来说，数据结构中存储了这张表中某一列的所有值，即是索引是基于表中的某一列创建的。换句话来说，一个索引是由表中的某一列数据组成，并且这些数据存储在某个数据结构中。

3．创建索引的时机

　　创建索引的基本原则：只在频繁查询的列上创建索引

  1. 应该创建索引的列的特点：
    1. 经常需要搜索的列上创建索引，可以提高搜索效率；
    2. 在作为主键的列上创建索引，强制该列的唯一性；
    3. 在经常用于连接的列上创建索引，主要是一些外键，可以提高连接速度；
    4. 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；在经常需要排序的列上创建索引，因为索引已经排序，可以利用索引的排序加快查询；
    5. 在经常使用在WHERE子句中的列上创建索引，加快条件的判断速度。
  2. 不应该创建索引的列的特点：
    1. 在查询中很少使用的列上不应该创建索引，因为这些列很少使用到，因此有索引或无索引，并不能提高查询速度，相反由于增加了索引，反而降低了系统维护速度，增大了空间需求；
    2. 在只有很少数据值的列上不应该创建索引，很少数据值的列如性别等，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大，增加索引，并不能明显加快检索速度；
    3. 当修改性能远远大于检索性能时，不应该创建索引，因为改性能和检索性能是互相矛盾的，当增加索引时，会提高检索性能，但会降低修改性能，当减少索引时，会提高修改性能，但会降低检索性能。因此，当修改性能远大于检索性能时，不应该创建索引。
  3. 可以在数据库设计器中创建三种索引：
    1. 唯一索引：不允许其中任何两行具有相同索引值的索引。
    2. 主键索引：表的某一列或列组合，其值唯一标识表中的每一行，该列或列组合称为表的主键。为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。
    3. 聚集索引：聚集索引表示表中存储的数据按照索引的顺序存储。由于聚集索引规定数据在表中的物理存储顺序，因此一个表只能包含一个聚集索引。

    4. 聚集索引实例：字典默认按字母顺序排序，如知道某个字的读音可根据字母顺序快速定位。

      非聚集索引：非聚集索引表示数据存储在一个地方，索引存储在另一个地方，索引带有指针指向数据的存储位置，需要查询两个地方才能查找到数据。一个表可以包含多个非聚集索引，可以为查找数据时常用的每个列创建一个非聚集索引。

      非聚集索引实例：如需查询某个生僻字，则需按字典前面的索引，如按偏旁进行定位，找到该字对应的页数，再打开对应页数找到该字。

      与非聚集索引相比，聚集索引通常提供更快的数据访问速度，但对数据更新影响较大。

4．索引的优缺点

  • 优点：创建索引的最大作用就是加快查询速度，它能从根本上减少需要扫描表的记录数。
    • 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
    • 可以大大加快 数据的检索速度，这也是创建索引的最主要的原因。
    • 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
    • 在使用分组和排序 子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
    • 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。
  • 缺点：
    • 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
    • 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
    • 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

5．索引分类

  • 普通索引：最基本的索引。

  • 组合索引：多个字段上建立的索引，能够加速复合查询条件的检索。

  • 唯一索引：与普通索引类似，但索引列的值必须唯一，允许有空值。

  • 组合唯一索引：列值的组合必须唯一。

  • 主键索引：特殊的唯一索引，用于唯一标识数据表中的某一条记录，不允许有空值，一般用primary key约束。

  • 全文索引：用于海量文本的查询，MySQL5.6之后的InnoDB和MyISAM均支持全文索引。由于查询精度以及扩展性不佳，更多的企业选择Elasticsearch。

6．索引优化

  • 分页查询很重要，如果查询数据量超过30%，MYSQL不会使用索引。

  • 单表索引数不超过5个、单个索引字段数不超过5个。

  • 字符串可使用前缀索引，前缀长度控制在5-8个字符。

  • 字段唯一性太低，增加索引没有意义，如：是否删除、性别。

  • 合理使用覆盖索引，如下所示：
select login_name, nick_name from member where login_name = ?

　　login_name, nick_name两个字段建立组合索引，比login_name简单索引要更快。

7．索引常用的数据结构

　索引的数据结构主要有4中，如下所示：

  1. 二叉查找树。

  1. B-Tree结构。

  2. B+-Tree结构。

  3. Hash结构。

　　Ｂ- 树是用于索引最常见的数据结构。这是应为B- 树有较好的时间效率，在查找、删除、插入操作上其时间复杂度都是对数阶，即O(logn)。

　　另外一个重要原因是，存储在B-树上的数据是有序的。通常，创建索引时使用哪种数据结构是由数据库决定的。但是，有些数据库，你可以指定使用哪种数据结构创建索引。

8．Hash索引

　　Hash表示另外一种可以被用作索引的数据结构，这种索引被称作hash索引。Hash表的查询效率是非常高的，尤其对比较字符串相等的查询，如果使用了hash索引，那么查询速度是极快的。例如，前面讨论过的查询语句(SELECT * FROM user WHERE name = ＇zhagnSan＇；),如果在name 列上创建hash索引，会显著提高该查询的效率。Hash索引的原理是，将列值作为hash表的key,而value中保存行的指针。Hash表就是一个关联数组(associative array，关联数组又称映射Map或字典Dictionary)，典型的结构看起来是这个样子：zhagnSan -> 0x28939。0x28939指向“zhagnSan”这一行在内存中的地址（Mysql 只有memory引擎支持Hash索引）。使用hash索引直接通过"zhagnSan"获取这一行在内存中的地址指针，明显比通过全表扫描查找出Employee_Name=’zhagnSan‘的行要快的多。

9．Hash索引的缺点

　　Hash表是无序的数据结构，在很多情况下，使用hash索引并不能提高效率。例如，你想查找出所有年龄小于40的员工，就不能使用hash索引。因为Hash索引只适用于键值对查询，即等值查询(例如"WHERE name=`zhagnSan`)，不能用于范围查询。Hash表中的键值映射隐含的告诉了你，hash表中的键并没有按照特定的顺序排序。而且hash表不如B- 树灵活，所以数据库系统通常会选择B-树作为索引的默认数据结构而不是hash表。

10．其他类型的索引

　　R- 树索引通常用来解决空间问题。例如，我要查找＇某某学校周边的美食＇，类似这种查询使用R-树索引会有很好的性能提升。空间数据库代表有PostGIS，MySQL Spatial。

　　还有一种位图(bitmap)索引，位图索引一般用在布尔类型的列上。这些列都具有低选择性(low selectivity)的特点。因为布尔类型的列只有1和0(True和False)两种值，假设这张表有10000条记录，该列的选择性为2/10000 ×100%=0.02%,这么低的选择性很适合很使用位图索引。更多关于索引的选择性问题，大力戳《不知道"选择性"怎么能说懂索引呢》。

11．索引是怎么提高查询效率的

　　索引的本质上是一个存储列值的数据结构。如果在某列上使用了B-树索引，那么这些列值在索引中是被排过序的，有序的值是索引能提高查询性能的主要原因。

　　当我们在Employee_Name列上创建了B-树索引后，再去执行前面提到的SQL语句时，数据库就不用再对Emplyee表做全表扫描了，而是直接从索引中查找名字叫“zhagnSan”的员工。由于B-树索引会把所有员工的名字按字母表顺序进行排序，这样以'J'开始的名字都会相邻，查找起来就会很快。值得注意的是，索引除了保存员工姓名还会保存该员工在数据表中所在行的指针，这样就可以检索到行中其他列的数据，以获取员工更多的信息。

开胃菜

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qiuhaitang/p/7913283.html