前端小姐姐也能看懂的“贪心算法”哦！
贪心算法是一种很常见的算法思想，而且很好理解，因为它符合人们一般的思维习惯。下面我们由浅入深的来讲讲贪心算法。
索引是什么？很多书和文章都会使用图书的目录来类比。目录的目的就是用方便我们查找具体内容的位置，具体的章节的范围。与此类似，MySQL中索引的用途是帮助我们加速查询以及排序。
在InnoDB中的索引类型有哈希索引、B+树索引、全文索引。哈希索引在InnoDB中设计为自适应的，不展开讨论。在InnoDB1.12之后有了全文索引，也是应用倒排，还没踩过坑(据说不支持中文)，有时间可以研究一下。
本篇主要讨论B+树索引。
B+树
学习MySQL的索引，必须得先了解其原理，否则很多问题将一头雾水。下文将讲述索引数据结构的原理，而不涉及其复杂的具体实现。
在谈B+树之前，不妨先思考，为什么索引能加快查询？为什么要用B+树作为索引而不用B树？哈希索引查询复杂度为O(1)为什么又不用哈希索引？
BST和AVL
在了解B树和B+树之前，先了解一下二叉搜索树(BST)和平衡二叉树(AVL)。
在顺序存储结构中(如数组)，最快的情况是第一个就是目标值，最坏的情况是最后一个是目标值，假设有n个元素，用大O标记法平均的时间复杂度为O(n)。
使用二叉搜索树可以有效的优化搜索时间。利用二叉搜索树的特性左子节点比父节点小、右子节点比父节点大，可以很方便的进行二分查找，有效优化的搜索时间。
正常情况下，我们使用二叉搜索树可以了，但如果出现以下的情况，二叉搜索树反而起不到效果，搜索的平均时间复杂度依旧为O(n)。
引入平衡二叉树，深度差不超过1，从而保证不倾斜，或者说更矮，保证其搜索效率。
B树和B+树
既然平衡二叉树已经可以加快查询了，但实际上InnoDB并不会使用。在思考B树和B+树的相关问题的时候，离不开一个问题——磁盘IO。索引文件存储在磁盘，假设有平衡二叉树树高30，那么你可能要扫描30次磁盘才能完成搜索。
对于需要磁盘IO的情况，使用平衡二叉树依旧比较糟糕，所以需要引入多路树，即B树和B+树，使得树更“矮”。
如果上述B树改成二叉树，那么树的高度就大了很多，换而言之就需要更多次的磁盘IO。
B+树是B树的变种。B+树的非叶子结点不存储数据，并且所有的叶子节点以双向链表的形式相连。
现在的索引模型基本都是B+树。
相对于B树来说，B+树的搜索更加稳定，因为B树有的数据是分布在非叶子节点上的。
B树的叶子节点以链表的形式相连且按照规则排了序，通过B+索引，可以更加方便的获取范围数据。
这也是不使用哈希索引的原因。虽然哈希索引搜索的时间复杂度为O(1)，但大部分时候我们并不会只查询一条记录，这种时候使用哈希索引就比较乏力了。
聚集索引
聚集索引，亦可称为主键索引。一张表只存在一个聚集索引。
聚集索引是根据其主键作为排序规则的B+树，搜索时根据其主键进行搜索。
其中叶子节点上存储着整条记录的数据。
InnoDB的B+树在磁盘中的存储是以数据页的形式，在树中间进行插入和删除操作涉及列“页分裂”和“页合并”的复杂过程(关于这点我个人也讲不明白，但可以类比AVL树的旋转去理解)，十分耗性能，而直接插入尾部是比较快捷的方式，所以在很多的规范中写道，当使用InnoDB引擎的时候，强烈建议用一个与业务无关的自增id作为主键。
此外，删除也是一样的，很多时候会要求做伪删除，不仅仅只是为了数据分析，更是为了索引的性能。
非聚集索引
非聚集索引又称辅助索引，以非主键列来建立。非聚集索引可以有多个。非聚集索引和聚集索引的区别在于，非聚集索引的叶子节点并不存储整条记录的数据，而是存储指向的主键的指针。所以，当利用非主键索引进行搜索时，还需要通过主键索引获取整条数据。
单值索引
单值索引就是在数据表单个列上建立单个值。
CREATE INDEX index_name ON table_name(column);
与主键索引类似，单值索引按照所指定列排序建立二叉树。当利用单值搜索到目标后，再通过主键索引去读取整条数据。
唯一索引
唯一索引与单值索引区别不大，只是唯一索引的值不会重复。
唯一索引除了能提高一些效率以外，有时也用来保证列的唯一性，如用户的手机号身份证等。这里不做过多赘述。
联合索引
创建联合索引时指定多列即可。
CREATE INDEX index_name ON table_name(column1, columm2, column3 [,…])
联合索引会按照建立索引时的顺序，对每个字段进行排序。即第一个字段排完序，接着排第二个字段，第三…
覆盖索引
在前面提到，非聚集索引搜索记录时还需要通过的主键索引，但如果查找的列刚刚好是联合索引的字段，那就没有必要去再去搜索主键索引，直接取叶子节点值即可，这就是覆盖索引。
为什么不用select *，原因就在此，不仅仅是为了减少读取更多列带来的开销，也是为了能够使用上覆盖索引。使用覆盖索引可以减少磁盘IO，有效提高性能。
下文将讲述有关联合索引的更多细节。
最左前缀原则
上文了解了联合索引，知道了联合索引的节点数据是按照建索引的顺序依次排序，由此我们引出了最左前缀原则，联合索引中，如果要用上索引字段，前面的字段不能跳过。如果上图的例子，假设是找column2=“ccc”的记录，大概的sql如下
SELECT some_column FROM table_name WHERE column2=”ccc”
这种情况下索引是用不上的，因为索引是先排序的column1，再排序column2，直接通过column2搜索，B+树并不知道怎么搜索。
索引失效
除了上述的最左前缀原则下索引的失效，还有其他索引失效情况。
使用MySQL内置函数运算的列索引会失效。
使用!=，is null，is not null 索引会失效。
比如你查找id != 500的记录，相当把扫描id<500，以及id >500的记录，本质上全表扫描没啥区别。
范围查询后的列无法使用。
还是用上图的例子，假设查询 column1 <= 4的情况
SELECT some_column FROM table_name WHERE column1 <= 4
因为column1是排了序的，索引联合索引column1还是可以使用上的，但column1是范围数据，在这范围内column2并不有序。
以通配符开头的模糊查询(LIKE “%string”)。
值得一提的是，LIKE “string%”是能用上索引的，类似于范围查询，查询从string开头的最小字符串到stirng开头的最大字符串。知道了LIKE “string%”是能用上索引的就能理解为什么LIKE “%string”为什么用不上索引了。
还有其他情况的情况，可用MySQL的查询分析器进行分析。
InooDB使用的锁是行锁，但如果在更新时索引失效了，行锁会变成表锁，在开发中应该避免。
索引使用tip
常用来分组和排序的字段可建立索引。
索引的作用是查询和排序，order by和group by是可以用上索引的，如果排序的有多字段，也是按照最左前缀原则。
经常用来查询的字段可建索引。
更新频繁的字段不要建立索引。
频繁更新的字段如果建立来索引，更新时不仅更新数据，而且索引的B+树也会发生变化，开销比较大，得不偿失。
选择性小的列不要建立索引。
比如说性别字段，只有男或女或未知，百万数据里只有这三个值，建立索引毫无意义。
索引尽量使用等值匹配。
尽量使用覆盖索引。
转载请注明：小猪云服务器租用推荐 » 好用易懂Mysql索引入门