在日常工作中，遇到查问数据比较慢的状况，个别是数据量很大，且没用到索引，索引就像书的目录，如果没有目录，须要一页一页的查问，效率很慢。有了目录，能够疾速的查找数据。

索引常见的三种模型

  • hash 表
  • 排序数组
  • 二叉查找树

hash 表是一种以键 - 值存储数据的构造，通过 key 间接间接找到对应的 vale。hash 表只实用等值查问场景，对范畴查找就生效了。

排序数组反对等值查问和范畴查问，在有序数组中，应用二分查找，查问的工夫复杂度是 O(logn)。从查问效率来说，有序数组的确是一个很好的抉择。然而须要增加或者删除数据时，为了保障数组的有序性，往两头插入的数据，须要挪动数组前面的数组，而内存的调配是很耗时的过程。

二叉树查找树也叫二叉搜寻树，它的特定是一个结点上左子树上所有的值都小于右子树上所有的值，能够将索引的值有序的保留在二叉树上，如下图所示。

查问的速度就是树的高度，节点每次的拜访都对应这磁盘的 IO 操作，同样的数据，为了放慢查问速度，须要升高树的高度，而升高树的高度，须要将二叉树转成 N 叉树。这里的 N 和mysql 查问的页的大小无关。

B+树结构

b+树的查找过程

如图所示，B+ 树是一个 N 叉树，每个节点有索引和指针。如果查找数据项28。

  • 首先会把磁盘块1加载到内存，此时产生一次IO,在内存中应用二分查找确定28在17和35之间
  • 找到磁盘1中的P2指针，通过磁盘1的P2指针指向的磁盘3加载到内存，产生第二次IO
  • 28在26和30之间，找到磁盘3的P2指针指向磁盘8，把磁盘8加载到内存中，产生第三次IO
  • 在内存中做二分查找找到28，总共三次IO

真实情况是，三层的 b+ 树能够示意上百万的数据，如果百万的数据只须要三次IO，性能将会很大的晋升，没有索引，查问每条数据都须要产生一次IO,查问的效率很低。

通过剖析，咱们能够晓得IO次数取决于b+树的高度，当数据肯定时，每个磁盘的数量越大，树的高度就越小，磁盘的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度就越低，所以在抉择索引字段的时候要尽量小，比方 int 4个字节要比 bigint 占8个字节少占一半。

B+树和B树的区别

  • b 树节点存储数据，b+树的节点不存储数据，只是存索引，数据都存储在叶子节点。
  • b+树叶子节点用链表串联起来，而b树没有。

创立索引的几个准则

  • 最左匹配准则，mysql 会始终向右匹配晓得遇到范畴查问（>、<、between、like）就进行匹配，比方a = 1 and b = 2 and c > 3 and d = 4 ,如果建设（a,b,c,d）程序的索引，d是用不到索引的。如果建设(a,b,d,c)的索引都能够用到，a、b、d的程序能够任意调整。
  • = 和 in 能够乱序，比方 a = 1 and b = 2 and c = 3 建设 （a,b,c）索引能够任意程序，mysql 查问优化器会优化查问索引
  • 尽量抉择区分度高的列作为索引，区分度指的字段的不重复性比例，比例越大，扫描的记录就越少，惟一键的区分度是1，而一些状态，性别区分度在数据量大的背后区分度就是0
  • 索引不能参加计算，放弃列的洁净，不能在索引列上增加函数，或者运算之类。因为b+树存储的是数据表的数据，而通过运算的数据和b+树上的数据不能做比拟，导致索引生效
  • 尽量的扩大索引，不要新建索引。比方表中原来有a的索引，当初要增加b的索引，把原来的索引扩大成（a,b)的索引即可。因为没建一个索引，就须要创立一个b+树。

参考

美团-MySQL索引原理及慢查问优化
深入浅出索引（上）

如果感觉文章对你有帮忙的话，请点个赞吧!