[10,15,18,20,21] | | | | | [x1,x4,x2,x3,x5]
下面的x是模拟数据再磁盘上的存储位置.这个时候如果我们需要查找15岁的人的名字.我们可以对盖数组进行二分查找.众所周知,二分查找的时间复杂度为O(logn).查找到之后再根据具体的位置去获取真正的数据.
PS:MySQL中的索引不是使用的数组,而是使用的B+树(后面讲),这里用数组举例只是因为比较好理解。
索引能为我们带来什么?
如上面所说,索引能帮助我们快速的查找到数据.其次因为索引中的值是顺序储存,那么可以帮助我们进行orderby操作.而且索引中也是存储了真正的值的,因此有一些的查询直接可以在索引中完成(也就是覆盖索引的概念,后面会提到).
总结一下索引的优点就是(《高性能》书中总结的):
- 减少查询需要扫描的数据量(加快了查询速度)
- 减少服务器的排序操作和创建临时表的操作(加快了groupby和orderby等操作)
- 将服务器的随机IO变为顺序IO(加快查询速度).
索引有哪些缺点呢?
首先索引也是数据,也需要存储,因此会带来额外的存储空间占用.其次,在插入,更新和删除操作的同时,需要维护索引,因此会带来额外的时间开销.
总结一下:
- 索引占用磁盘或者内存空间
- 减慢了插入更新操作的速度
实际上,在一定数据范围内(索引没有超级多的情况下),建立索引带来的开销是远远小于它带来的好处的,但是我们仍然要防止索引的滥用.
都有哪些类型的索引?
对于MySQL来说,在服务器层并不实现索引,而是交给存储引擎来实现的,因此不同的存储引擎实现的索引类型不太一样.InnoDB作为当前使用最为广泛的存储引擎,使用的是B+树索引,因此我们大部分时间提到的索引也都是指的它.
MySQL主要有以下几种索引:
- B-树索引/B+树索引
- 哈希索引
- 空间数据索引
- 全文索引
本文只学习B-树索引和B+树索引.
B-树索引和B+树索引
这里不会特别详细的解释B-树和B+树的数据结构原理,有兴趣的小伙伴可以移步参考文章中的文章.或者通过google自行了解.
B-树
B-树是一棵多路平衡查找树,对于一棵M阶的B-树有以下的性质:
- 根节点至少有两个子女.
- 每个节点包含k-1个元素和k个孩子,其中m/2 <= k <= m.
- 每一个叶子节点都包含k-1个元素,其中m/2 <= k <= m.
- 所有的叶子节点位于同一层.
- 每个节点中的元素从小到大排列,那么k-1个元素正好是k个孩子包含的值域的划分.
这么说可能会有一些难理解,可以将B-树理解为一棵更加矮胖的二叉搜索树.
B+树
B+树是B-树的进阶版本,在B-树的基础上又做了如下的限制:
- 每个中间节点不保存数据,只用来索引,也就意味着所有非叶子节点的值都被保存了一份在叶子节点中.
- 叶子节点之间根据自身的顺序进行了链接.
这样可以带来什么好处呢?
- 中间节点不保存数据,那么就可以保存更多的索引,减少数据库磁盘IO的次数.
- 因为中间节点不保存数据,所以每一次的查找都会命中到叶子节点,而叶子节点是处在同一层的,因此查询的性能更加的稳定.
- 所有的叶子节点按顺序链接成了链表,因此可以方便的话进行范围查询.
怎样创建高性能的索引?
由于优化索引和优化查询一般是分不开的,因此这一块可能会包含部分的查询优化内容.
前缀索引和索引选择性
如果希望给一个很长的字符串上添加索引,那么可以考虑使用前缀索引.在正式介绍前缀索引之前,我们先大概考虑一下索引的工作步骤,数据库使用索引进行查找的时候,一般是如下几步:
- 在索引的B+树上找到对应的值,比如找到学校名称为
卡塞尔学院的一条记录,并且拿到这条数据在磁盘上的地址. - 根据地址去磁盘上查找,拿到该条数据所有的值.
那么假如在所有的学校名称的值中,卡塞尔就可以唯一的标识这条数据,那么用卡塞尔来做索引是否可以达到和卡塞尔学院做索引相同的效果?
答案是肯定的,而使用卡塞尔的话,是可以减少索引的大小到原来的60%的.这就是前缀索引的作用.
前缀索引: 在对一个比较长的字符串进行索引时,可以仅索引开始的一部分字符,这样可以大大的节约索引空间,从而提高索引效率.但是这样也会降低索引的选择性.
索引的选择性: 不重复的值/所有的值. 可以看出索引的选择性为0-1,最高的就是该列唯一,没有重复值.所以唯一索引的效率是比较好的.
但是在一般情况下,较长的字符串的一些前缀的选择性也是比较好的,这个我们可以算出来.使用下面的语句：
select count(distinct left(school_name,3))/count(*) as sch3, count(distinct left(school_name,4))/count(*) as sch4, count(distinct left(school_name,5))/count(*) as sch5, count(distinct school_name)/count(*) as original from user;
