什么是索引
索引是对数据库表中一列或多列的值【排好序】的数据结构。
为什么要加索引
因为创建索引可以大大提高系统的查询性能。
怎么提高查询性能的
简单的理解:一张数据量比较大的表格如果没有添加任何索引,那我们在执行查询的时候
就会是进行全表扫描,逐行比对,这样的读取效率肯定很低,如果我们为数据创建了索引
索引的实现方式又是支持快速查询的这样我们只需要先查询索引中符合条件的,
然后再通过索引指向的数据行位置就可以实现快速定位数据了,不用全表扫描了。
索引存储在什么地方
数据库索引是存储在磁盘上,当表中的数据量比较大时,索引的大小也跟着增长,达到几个G甚至更多。
当我们利用索引进行查询的时候,不可能把索引全部加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页就对应索引树的节点。
为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询,为何Mysql选择B+树?
哈希表
哈希表可能会出现哈希冲突。
最主要的原因是它不支持范围查询。
完全平衡二叉树
如图如果一个树的高度很大,如果查询的数据刚好在叶子节点那经历的磁盘Io的次数就是这个数的高度。
所以极端情况下平衡二叉树也不是优选。
B-Tree
先说说几个概念:
- 度(节点的数据存储个数)也就是说B-Tree上的一个节点可以存储多个数据。
- 叶节点具有相同的深度
- 叶节点的指针为空
- 节点中的数据从左到右递增排列
这的确解决了树的高度问题,因为:B-Tree的节点可以存储多个值,高度肯定小于平衡二叉树,磁盘io的次数也会少。
但是在范围查找方面较比B+Tree差点。
题外话:B-Tree和BTree是一种树。
B+Tree
B+Tree是B-Tree的变种,
B+树的表示要比B树要“胖”,原因在于B+树中的非叶子节点会冗余一份在叶子节点中,并且叶子节点之间用指针相连。
mysql的实现中,B+Tree是把非叶子节点中只存储索引,不存储数据,只有叶子节点存储数据,这样节点中的空间更多的存储了索引,增加了度。
最大程度的降低了树的高度,再加上一个节点的大小设置成为一页或页的倍数,一次磁盘io就可以读出了一个节点中的很多数据。
加载到内存中再进行查找就很快了
所以最后总结:
使用B+Tree:可以提高查询索引时的磁盘IO效率,并且可以提高范围查询的效率,并且B+树里的元素也是有序的。
MyISAM和InnoDB的B+Tree实现
MyISAM中的B+Tree
MYISAM中叶子节点的数据区域存储的是数据记录的地址.
MyISAM的索引是单独一个文件存放的。
MyISAM中的主键索引和辅助引是没有区别的,其叶子节点存放的都是数据记录的地址。
InnoDB中的B+Tree
InnoDB中的叶子节点数据区域存储的内容和主键索引和辅助索引引有关。
如果是主键索引存储的就是索引+数据(index+data)
Innodb的主键索引要比MyISAM的主键索引查询效率要高,因为找到主键索引就找到了数据,MyISAM还有通过地址查询一次。
如果是辅助索引存储的是主键的值
因此可以看出InnoDB的辅助索引会发生两次,一次通过辅助索引查询主键索引,一次是通过主键索引查询到数据。
InnoDB的索引是和数据文件放在一起的。
聚集索引和非聚集索引
聚集索引
数据行的物理顺序与列值(一般是主键的那一列)的逻辑顺序相同,一个表中只能拥有一个聚集索引。
-
聚集索引的叶子节点存放有对应的数据节点,可以直接获取到对应的数据,
- 如果不创建索引,系统会自动创建一个隐含列作为表的聚集索引。
- 最好还是在创建表的时候添加聚集索引
- 在经常用于查询或聚合条件的字段上建立聚集索引。这类查询条件包括 between, >, <,group by, max,min, count等。
缺点: -
插入和更新索引的速度会比较慢,因为将会导致被更新的行移动。
非聚集索引
数据行的物理顺序与列值的逻辑顺序不相同,一个表中可以拥有多个非聚集索引。
-
叶子节点存放的不是实际数据,而是指向实际数据的指针。
-
聚集索引以外的索引都是非聚集索引,细分可以分为:普通索引,唯一索引,全文索引
注意:
InnoDB 主键使用的是聚簇索引,MyISAM 不管是主键索引,还是二级索引使用的都是非聚簇索引
创建索引的依据
什么样的字段适合建索引
索引是建立在数据库表中的某些列的上面。因此,在创建索引的时候,应该仔细考虑在哪些列上可以创建索引,在哪些列上不能创建索引。 一般来说,应该在具备下述特性的列上创建索引:
- 第一、在经常需要搜索的列上,可以加快搜索的速度;
- 第二、在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构;
- 第三、在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度;
- 第四、在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的;
- 第五、在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;
- 第六、在经常使用在WHERE子句中的列上面创建索引,加快条件的判断速度。
建立索引,一般按照select的where条件来建立,
比如: select的条件是where f1 and f2,那么如果我们在字段f1或字段f2上建立索引是没有用的,只有在字段f1和f2上同时建立索引才有用等。
什么样的字段不适合建立索引
- 对于那些在查询中很少使用或者参考的列不应该创建索引
- 对于那些只有很少数据值的列也不应该增加索引,比如:性别,状态,这是因为,由于这些列的取值很少,创建索引效果也不明显。
- 对于那些定义为text, image和bit数据类型的列不应该增加索引
记住这些可以提高索引的使用效率
资源
数据结构:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
面试必备之Mysql索引底层原理分析
为什么数据库选B-tree或B+tree而不是二叉树作为索引结构
关于B-树问题的演示图解