个人博客

一、简介

索引是帮助数据库高效获取数据的数据结构，索引是基于数据表创建的，它包含了表中某些列的值以及记录对应的地址，并把这些值存储在一个数据结构中。索引采用的数据结构有hash、平衡二叉树、B树、B+树。

二、索引的数据结构

1，hash：

hash表，也叫做散列表，是根据键值直接访问的数据结构。它用hash函数计算出键值，通过键值映射到表中的一个位置来访问记录，从而加快查找速。这个存放记录的表就叫hash表。

比如，使用select * from table where name = "test"; 这时，会先计算出字符“test”的hash值，然后根据下表位置直接访问到数据，效率很高，但是不能做范围查询。

优点：查找可以直接根据key值访问。

缺点：不能进行范围查找。

2，平衡二叉树：

平衡二叉树，又叫做AVL树。它除了具备二叉查找树的特征外，还有一个重要的特性，就是它的左子树和右子树都是平衡二叉树，左子树和右子树的深度之差的绝对值不会超过1。

通过平衡二叉树建立id索引，平衡二叉树会选择一个中间值，中间值的左边为左子树，中间值的右边为右子树。左子树值<中间值<右子树值。

如果利用平衡二叉树建立索引的话，会生成一个文件。如果有1亿条数据，就有建立1亿个节点。查询的时候，如果全部数据加载到内存，然后再进行比较，容易导致内存不足。一般操作的时候，都是一个一个数据的取，对比数据不相等后往左子树或者往右子树取下个数据。

如图中的平衡二叉树，如果要查找7，就要经历4次IO操作。依次获取的值为4 > 8 > 6 > 7。

优点：平衡二叉树算法基本和二叉树查询相同，效率比较高。

缺点：虽然支持范围查询，但回旋查询效率低。

特点：如果树的高度越高，那么IO查询的次数就会越多。

3，B树：

B树是一种树状数据结构，它能够存储数据并对数据进行排序，可以以O(log n)的时间复杂度进行查找、顺序查找、插入和删除数据。B树是一个节点能拥有多于2个子节点的二叉查找树。与平衡二叉树不同，B树为系统优化大块数据的读和写操作。B树的节点元素比平衡二叉树要多，能减少树的高度，实现减少IO的操作。它是对平衡二叉树的改进。

如图中的B树，如果要查找7，就要经历3次IO操作。依次获取的值为4 > 6, 8> 7。

优点：B树中节点可以有多个元素，减少IO操作，所以B树的查询效率比平衡二叉树高。

缺点：范围查询效率还是比较低。

4，B+树：

B+树继承了B树的特征，新增了叶子节点和非叶子节点的关系，叶子节点包含了key和value，非叶子节点只包含了key。所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定的顺序，因此范围查询效率高。

优点：B+树解决了范围查询效率问题，减少IO的操作。

缺点：因为有冗余的节点数据，会比较占应硬盘空间。

三、myisam和innodb的索引

myisam和innodb都是使用B+树进行建立索引，但是两者使用的方式略有不同。

myisam引擎使用B+树作为索引的数据结构，叶节点的value存放的是数据记录的地址，然后再通过地址查找数据。

而innodb引擎使用也是B+树作为索引的数据结构，但是叶节点的value存放的是那一行的数据，直接获取。相比之下，效率会比myisam引擎高些，但是比较占硬盘空间。

myisam的索引文件和数据文件是分离的，索引文件只保存数据记录的地址。而innodb表数据文件本身就是按B+树结构进行存储的，这棵树的叶节点的value保存了完整的数据记录。这个索引的key就是数据表的主键，因此innodb表数据文件本身就是索引文件。

四、索引失效问题

• 索引无法存储null值，where语句中避免null值判断，否则扫描全表。
• 如果条件中有or，即使条件中有索引也不会使用。只有在or的条件字段都有索引的时候，索引才会生效。
• 对于联合索引（多列索引），如果不是使用前部分字段，则不会使用索引。
• like查询以%开头的，不会使用索引，%后置才会使用索引。
• 使用不等式!=或者<>，则不会使用索引。
• 使用not in 或者not exist，不使用索引。

五、索引的分类

• 普通索引index：加速查找。
• 唯一索引：主键索引primary key，加速查找和约束（不为空且唯一）；唯一索引unique，加速查找和约束（唯一）。
• 联合索引：primary key(id, name)，联合主键索引；unique(id, name)，联合唯一索引；index(id, name)，联合普通索引。
• 全文索引fulltext：用于搜索很长的一篇文章的时候，效果好。
• 空间索引spatial：对于空间数据的搜索，我们需要空间索引spatial index来提升搜素效率。

mysql多列索引使用最左前缀匹配原则，优先匹配左边的字段，依次往后推。对于顺序比较有要求：

• 选择性高的列放最左边。
• 把长度小的列放最左边（单页可以获得更多的数据）。
• 使用最频繁的列放最左边。

六、SQL查询优化

开启慢查询日志，可以让mysql记录下查询超过一定时间的sql语句，通过定位分析优化系统性能。

mysql数据库配置慢查询的相关参数：

• slow_query_log 慢查询开启状态。
• slow_query_log_file 慢查询日志存放的位置。
• long_query_time 查询超过多少秒才记录。