数据库索引 / 开普饭

索引（index）是帮助MySQL高效获取数据的数据结构。常见的查询算法：顺序查找、二分查找、二叉树查找、哈希散列、分块查找、B树。

　　1）哈希算法：就是把任意长度值（key）通过散列算法变成固定长度的key地址，通过这个地址进行访问的数据结构。它通过关键码值映射到表中一个位置来访问记录，以加快查找速度。时间复杂度为O(1)，寻址查询，不适用于范围查询，无法排序。

　　2）二叉树：它的左子节点值比父节点值小，右子节点值比父节点值大。时间复杂度为O(logN)，缺点：不平衡二叉树。

　　3）B树：度（degree）-节点的数据存储个数；叶节点具有相同的深度且指针为空；叶节点的数据key从左到右递增排序。

　　4）B+树：真实的数据存在于叶子节点，非叶子节点不存储真实的数据，只存储指引搜索方向的数据项。

常见的索引原则：

　　1）选择唯一性索引：唯一性索引的值是唯一的，可以更快速地通过该索引来确定某条记录。

　　2）为常作为查询条件的字段建立索引、为经常需要排序、分组和联合操作的字段建立索引。

　　3）限制索引的数目：越多的索引，会使更新表变得很浪费时间。

　　4）尽量使用数据量少的索引：如果索引的值很长，那么查询的速度会受到影响。

　　5）尽量使用前缀来索引：如果索引字段的值很长，最好使用值得前缀来索引。

　　6）删除不再使用或很少使用的索引。

　　7）最左匹配原则，是非常重要的原则。

　　8）尽量选择区分度高的列作为索引。

　　9）索引列不能参与运算，带函数的查询不能参与索引。

　　10）尽量的扩展索引，不要新建索引。

创建索引

　　1）创建表时，创建索引：

　　　　create table 表名 (字段数据类型 , [unique | fulltext | spatial][index | key] 索引名称 (被索引字段名[length]) [asc | desc] );

1 CREATE TABLE book ( 2     bookid INT NOT NULL, 3     bookname VARCHAR(255)NOT NULL, 4     year_publication YEAR NOT NULL, 5     UNIQUE INDEX UniquId(id),     ##唯一索引 6     INDEX(year_publication),    ##普通索引 7     INDEX SingleIdx(bookname(20)),    ##单列索引 8     INDEX MultiIdx(bookid,bookname(100)),    ##组合索引 9     FULLTEXT INDEX FullTextIdx(bookname)，    ##全文索引（只支持MyISAM—>engine=MyISAM）10     g GEOMETRY NOT NULL,11     SPATIAL INDEX spatIdx(g)    ##空间索引（存储引擎必须为MyISAM且空间类型的字段为空值）12 );

　　2）在已经存在的表上创建索引：

　　　　a. 使用 alter table 创建索引：alter table 表名 add [unique | fulltext | spatial] [index] 索引名称 (被索引字段名[length]) [asc | desc];

　　　　　　例：alter table book add index BknameIdx(bookname(30));

　　　　b. 使用 create index 创建索引：create [unique | fulltext | spatial] [index] 索引名称 on 表名 (被索引字段名[length]) [asc | desc];

删除索引

　　1）使用 alter table 删除索引：alter table 表名 drop index 索引名称;

　　　　例：alter table book drop index BknameIdx;

　　2）使用 drop index 删除索引：drop index 索引名称 on 表名;

查看索引

　　show index from 表名;

索引的分类：唯一索引/非唯一索引、主键索引（主索引）、聚集索引/非聚集索引、组合索引。

　　1）唯一索引是在表上一个或者多个字段组合建立的索引，这个或者这些字段的值组合起来在表中不可以重复。

　　　　　　如下表中，为“学号”建立索引：

　　　　　　　　学号　　　　姓名

　　　　　　------------------------------------

　　　　　　　　001　　　　张三

　　　　　　　　002　　　　李四

　　2）非唯一索引是在表上一个或者多个字段组合建立的索引，这个或者这些字段的值组合起来在表中可以重复，不要求唯一。

　　　　　　如下表，为Score建立索引，可不唯一：

　　　　　　　　Score　　　　Name

　　　　　　　　 98　　　　　张三

　　　　　　　　 98　　　　　李四

　　3）主键索引（主索引）是唯一索引的特定类型。表中创建主键时自动创建的索引。一个表只能建立一个主索引。

　　4）聚集索引（聚簇索引）：表中记录的物理顺序与键值的索引顺序相同。一个表只能有一个聚集索引。

　　扩展：聚集索引和非聚集索引的区别？分别在什么情况下使用？

　　　　聚集索引和非聚集索引的根本区别是表中记录的物理顺序和索引的排列顺序是否一致。

　　　　聚集索引的表中记录的物理顺序与索引的排列顺序一致。

　　　　　　优点是查询速度快，因为一旦具有第一个索引值的记录被找到，具有连续索引值的记录也一定无力的紧跟其后。

　　　　　　缺点是对表进行修改速度较慢，这是为了保持表中的记录的物理顺序与索引顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排，降低了执行速度。在插入记录时数据文件为了维持B+树的特性而频繁的分裂调整，十分低效。

　　　　建议使用聚集索引的场合为：

　　　　　　a. 某列包含了小数目的不同值；

　　　　　　b. 排序和范围查找；

　　　　非聚集索引的记录的物理顺序和索引的顺序不一致。

　　　　其他方面的区别：

　　　　　　a. 聚集索引和非聚集索引都采用了B+树结构，但非聚集索引的叶子层并不与实际的数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针的方式。聚集索引的叶子节点就是数据节点，而非聚集索引的叶子节点仍然是索引节点。

　　　　　　b. 非聚集索引添加记录时，不会引起数据顺序的重组。

　　　　看上去聚簇索引的效率明显要低于非聚簇索引，因为每次使用辅助索引检索都要经过两次B+树查找，这不是多此一举吗？聚簇索引的优势在哪？

　　　　　　由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键id来组织数据，获得数据更快。

　　　　　　辅助索引使用主键作为“指针”，而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时，辅助索引的维护工作，Innodb在移动行时无需更新辅助索引中的这个“指针”。也就是说行的位置会随着数据库里的数据的修改而发生变化，使用聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。

　　　　建议使用非聚集索引的场合为：

　　　　　　a. 此列包含了大数目的不同值；

　　　　　　b. 频繁更新的列；

　　5）组合索引（联合索引）：基于多个字段而创建的索引就称为组合索引。　　　　

　　　　　　创建索引

　　　　　　create index idx1 on table1(col1,col2,col3);

　　　　　　查询

　　　　　　select * from table1 where col1=A and col2 =B and col3 = C;

　　　　举例说明：给出一个多列索引(username,password,age)，当三列在where中出现的顺序如(username,password,age)、(username,password)、(username)才能用到索引，如下面几个顺序（password,age）、(password)、(age)---这三者不从username开始，（username,age）---断层，少了password，都无法利用到索引。因为B+树多列索引保存的顺序是按照索引创建的顺序，检索索引时按照此顺序检索。　

数据库索引的原理（实现）

MyISAM索引实现

　　MyISAM引擎使用B+树作为索引结构，叶子节点的data域存放的是数据记录的地址。在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

　　MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引，如果指定的key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”。

InnoDB索引实现

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

　　第一个重大区别是InnoDB的数据文件本身就是索引文件。在InnoDB中，表数据文件本身就是B+树组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这种索引也叫做聚集索引。

　　第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。　　

索引的优缺点

　　优点：大大加快了数据的检索速度；

　　　　　创建唯一性索引，保证数据库表中每行数据的唯一性；

　　　　　加速表和表之间的连接；

　　　　　在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。

　　缺点：索引需要占物理空间；

　　　　　当对表中的数据进行增加、删除和修改时，索引也要动态的维护，降低了数据的维护速度。

辅助索引

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

为什么不建议使用过长的字段作为主键？

　　因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。

B树的查找过程

　　如上图所示，如果要查找数据项为29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万此次的IO，显然成本非常高。

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

　　最左匹配原则中where字句有or出现还是会遍历全表。

性别字段为什么不适合加索引？从B+树原理解释。

　　尽量选择区分度高的字段作为索引，区分度的公式是count(distince col)/count(*)，表示字段不重复的比例，比例越高我们扫描的记录数越少，唯一键的区分度为1，而一些状态、性别字段可能在大数据面前区分度为0。在性别字段上增加索引，并不能明显加快索引速度。

MySQL的B+树索引的优点？为什么不用二叉树？B树和B+树为什么比红黑树更合适？

　　数据库文件很大，需要存储到磁盘上，索引的结构组织要尽量减少查找过程中磁盘IO的读取次数。

　　1）高度原因

　　　　B+树中的每个节点可以包含大量的关键字，这样树的深度降低了，所以任何关键字的查找必须走一条从根节点到叶子节点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率相当，这就意味着查找一个元素只要很少节点从外存磁盘中读入内存，很快访问到要查询的数据，减少了磁盘IO的读取次数。

　　2）磁盘预读原理和局部性原理

　　　　将一个节点的大小设为等于一个页（16k），这样每个节点只需要一次IO就可以完全载入。

数据库索引

相关推荐