2018-10-08

数据库索引

索引的优点：

通过创建唯一索引，可以保证数据库表中每行数据的唯一性
可以加快查询速度
在实现数据的参考完整性方面，可以加速表和表之间的连接
在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间
通过使用索引，可以在查询中使用优化隐藏器，提高系统的性能

索引缺点：

创建和维护索引要耗费时间，并其随着数据量的增加耗费时间也增加
索引占用空间内存
在对表中数据进行增加删除和修改的时候，索引也需要动态维护，降低了数据维护速度

索引分类：
普通索引
唯一索引
复合索引：多个列上建立索引，叫做复合索引(组合索引)
聚集索引：表中行的物理顺序与逻辑顺序相同，一个表只能包含一个聚集索引
非聚集索引

索引失效：

WHERE字句的查询条件里有不等于号，mysql将无法索引
WHERE字句的查询条件里使用了函数
在JOIN操作中，mysql只有在主键和外键的数据类型相同时才能使用索引
如果WHERE子句的查询条件里使用了比较操作符LIKE和REGEXP，mysql只有在搜索模板的第一个字符不是通配符的情况下才能使用索引
在ORDER BY操作中，MYSQL只有在排序条件不是一个查询条件表达式的情况下才使用索引。尽管如此，在涉及多个数据表的查询里，即使有索引可用，那些索引在加快ORDER BY操作方面也没什么作用。
如果某个数据列里包含着许多重复的值，就算为它建立了索引也不会有很好的效果。比如说，如果某个数据列里包含了净是些诸如“0/1”或“Y/N”等值，就没有必要为它创建一个索引。
如果条件中有or(并且其中有or的条件是不带索引的)，即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)。注意：要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引。
如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引。
如果mysql估计使用全表扫描要比使用索引快,则不使用索引。

什么情况下适合建立索引：
经常用作查询的字段
在经常用作表连接的属性上，加快连接速度
在经常使用where子句中的列上创建索引，加快条件的判断速度
在经常需要排序的列上创建索引
在经常需要根据范围进行搜索的列上创建索引
考虑使用索引覆盖，对数据很少被更新的表，如果用户经常只查询其中的几个字段，可以考虑在这几个字段上建立索引

索引的实现：
InnoDB：B+Tree
数据文件本身就是索引文件
聚集索引：表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录
必须有主键，如果没有显式指定，系统会自动选择一个可以作为唯一标识数据
所有的辅助索引都引用主键作为data域

MyISAM：B+Tree
叶子节点的data域存放的数据记录的地址
索引算法为按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出data域的值，然后以data域的值为地址，读取相应的数据记录
主索引和辅助索引的存储结构没有任何区别
索引文件和数据文件是分开的，索引文件仅保存数据记录的地址

memory：适用于快速访问数据的场景。内部基于哈希表数据结构的实现，只包含哈希值和行指针。为了解决多个hash冲突问题，采用了链地址法来解决冲突问题

B树和B+树：
B树：
B树中每个结点包含了键值和键值对于数据对象存放地址的指针，所以成功搜索一个对象可以不用到达树的叶节点
在B树中查找给定关键字的方法：首先把根节点取出，在根节点所包含的关键字k1....kj查找给定的关键字，若找到则查找成功，若未找到，则确定要查找的关键字在某个k1或ki+1之间，于是取pi所指的下一层索引结点继续查找，直到找到或者直到为空

B+树：
非叶节点中存放的关键码并不指示数据对象的地址指针，非叶节点指示索引部分，所有叶节点在同一层上，包含全部关键码和相应数据对象的存放地址指针，且叶节点按关键码从小到大顺序连接
有两个指针，一个是树的根节点，一个是最小关键码的叶节点
有两种搜索方式：
按叶节点进行链表的顺序搜索
从根节点开始搜索，和B树类似，无论搜索成功与否，都将走完树的所有层
数据对象的插入和删除仅仅在叶节点上进行

区别：
B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶节点中，并且有可能在非叶节点中也有可能重复出现，以维持B+树的平衡
因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中
B树的查询效率与键在数中的位置有关，最大时间复杂度与B+树相同(在叶节点的时候)，最小时间复杂度为1(在根节点的时候)。而B+树的时间复杂度对某建成的树是固定的