深入理解数据库索引

1. 索引的目的

数据库索引的目的在于提高检索效率,例如我们要在字典中查询“MySQL”这个单词,是不是先要查询M开头的单词表,然后在查询第二个字母为y的单词,然后缩小范围继续找,直到找到“MySQL”这个单词为止。这就好像我们沿着一个树,从树根开始找,沿着主干、树干、到最后的末梢,走了其中的一条路径。这比查询一个链表的结构效率要高得多。

2. 关于B树和B+树

2.1 B树

B树,多路平衡树,每一个节点存储数据项key/data和指针,在同一个节点中数据是增序的,每个节点最多k个子节点,k的大小取决于磁盘页的大小,所有的叶子节点都在同一层。B树的结构可参考下图:
image

可以看到每个磁盘块包含几个数据项和指针,如磁盘块1包含数据项17和35,包含指针P1、P2、P3,P1表示小于17的磁盘块,P2表示在17和35之间的磁盘块,P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据,只存储指引搜索方向的数据项,如磁盘块1中的17、35并不真实存在于数据表中。

B-Tree大大降低了二叉树的高度,所以也就极大地提升了查找性能。

2.2 B+树

B树结构图中可以看到每个节点中不仅包含数据项的key值,还有data值。而每一个节点的存储空间是有限的,如果data值较大时将会导致每个节点能存储的key的数量很小,这样会导致B-Tree的高度变大,增加了查询时的磁盘I/O次数,进而影响查询性能。而B+树叶子节点只存储数据项的data值,叶子节点之间通过双向链表链接,非叶子节点只存储指针和数据项的key值,因为非叶子节点内部没有数据项的data,有更多的空间存放key,所以B+树的出度一般比B树要大,树的深度就小,因此以B+树的磁盘检索效率比B树高,B+树的结构示意图如下:
image

如图所示,如果要查找数据项87,那么首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定87在P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计,通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,87在79之后,锁定磁盘块3的P2指针,通过指针加载磁盘块9到内存,发生第三次IO,同时内存中做二分查找找到87,结束查询,总计三次IO。真实的情况是,3层的B+树可以表示上百万的数据,如果上百万的数据查找只需要三次IO,性能提高将是巨大的,如果没有索引,每个数据项都要发生一次IO,那么总共需要百万次的IO,显然成本非常高。

2.3 为什么要使用B+树

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。在计算机中,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。预读的长度一般为页(Page)的整数倍。
数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为操作系统的页大小的整数倍,这样每个节点只需要一次I/O就可以完全载入。InnoDB存储引擎中也有页(Page)的概念,页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB。
一般表的主键类型为BIGINT(占8个字节),指针类型也一般为8个字节,也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值,为方便计算,这里的K取值为10^3)。三层B+树最多可以存储10亿条记录。B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要1到3次磁盘I/O操作。

随机I/O对于MySQL的查询性能影响非常大,而顺序读取磁盘中的数据会很快,由此我们也应该尽量减少随机I/O的次数,这样才能提高性能。在B树中由于所有的节点都可能包含目标数据,我们总是要从根节点向下遍历子树查找满足条件的数据行,这会带来大量的随机I/O,而B+树所有的数据行都存储在叶子节点中,而这些叶子节点通过双向链表依次按顺序连接,当我们在B+树遍历数据(比如说范围查询)时可以直接在多个叶子节点之间进行跳转,保证顺序、倒序遍历的性能。

3. MySQL索引实现

3.1 MyISAM引擎索引

MyISAM使用B+树作为索引的结构,叶子结点的数据域存放的是行记录的地址。如下图所示:

image

以Col1列作为主键索引的示意图,可以看到,叶子结点的data域存放的是数据记录的地址。如果我们在字段Col2上建一个辅助索引(非主键索引),那么索引的结构如下:
image
MyISAM首先按照B+树的搜索算法查询索引,如果指定的key存在,则取出data域的值,然后用data域的地址查询数据记录。MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址,因此MyISAM的索引方式也叫做非聚集的,之所以这么称呼是为了与InnoDB的聚集索引区分。这里的聚集是指索引和数据是否在一起

3.2 InnoDB引擎索引

InnoDB的索引实现方式与MyISAM的索引实现方式的区别有两个:

  • InnoDB的数据文件本身就是索引文件。在InnoDB中,数据文件本身就是按B+树组织的一个索引结构。叶子结点保存了完整的数据记录,这种索引叫做聚集索引。聚集索引这种实现方式使得按主键搜索十分高效,直接能查出整行数据。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形;
  • InnoDB叶子节点的data域存储的是相应记录主键的值而不是地址;
    image

InnoDB的非主键索引(以其他列作为索引)data域存储相应记录主键的值。换句话说,InnoDB的所有非主键索引都引用主键的值作为data域。如下图所示:

image

由上可知,使用非主键索引搜索时需要检索两遍索引,首先检索非主键索引获得主键(Primary Key),然后用主键到主键索引树中检索获得完整记录。

为什么非主键索引结构叶子节点存储的是主键值,而不像主键索引那样直接存储完整的一行数据,这样就能避免二次检索?显然,这样做一方面节省了大量的存储空间,另一方面数据冗余较少,更新数据的效率较高,不用担心数据一致性的问题。

到了这里也很容易明白为什么不建议使用过长的字段作为主键,因为所有的非主键索引都引用主键值,过长的主键值会让非主键索引变得过大。

4. 最左前缀匹配

当B+树的数据项是复合的数据结构,比如以(name,age,sex)三列作为索引的时候,此时索引类型就是联合索引,B+树是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,B+树会优先比较name来确定下一步的搜索方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候,B+树就不知道下一步该搜索哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。比如当(张三,F)这样的数据来检索时,B+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了。这个是非常重要的性质,即MySQL建立联合索引时会遵守的最左前缀匹配原则,在检索数据时从联合索引的最左边列开始匹配。

保持最左前缀匹配原则,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的顺序可以任意调整。

5. 建立索引原则

  • 在使用InnoDB作为存储引擎时,如果没有特殊需要,请永远使用一个与业务无关的自增字段作为主键,而且这个字段长度不宜过大。为什么?InnoDB使用聚集索引,数据记录本身存放在主索引(B+树)的叶子结点上,这就要求同一个叶子结点(大小为一个内存页或磁盘页)的数据记录按主键顺序存放,每当一条新的记录插入时,mysql会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。如果使用自增主键,那么每次插入新的记录,记录就会顺序插入到当前节点的下一个位置。这样就会形成一个紧凑的索引结构,每次插入不需要移动已有数据,因此效率很高;
  • 如果使用非自增主键(例如身份证号或学号这种无序字符串),每次插入主键近似随机,每次记录都要插入到现有索引页的中间的某个位置,这时不得不移动元素来完成插入,就增加了很多开销;
  • 为经常需要排序、分组和联合操作的字段建立索引;
  • 为常作为查询条件的字段建立索引;
  • 限制索引的数目,索引不是越多越好,太多的索引会使插入和更新变慢,因为需要维护索引树;
  • 尽量选择区分度高的列作为索引,区分度的公式是count(distinct column)/count(*),表示字段不重复的比例,比例越大我们扫描的记录数越少,唯一索引的区分度是1;
  • 删除不再使用或很少使用的索引;
  • 尽量的扩展索引,而不是新建索引,能使用组合索引就不要新建索引;
  • 索引列不能参与计算,比如from_unixtime(create_time) = ’2019-05-21’就不能使用到索引,原因很简单,b+树中存的都是数据表中的字段值,但进行检索时,需要把所有元素都应用函数才能比较,显然成本太大。所以语句应该写成create_time = unix_timestamp(’2019-05-21’);

6. 参考资料

以上内容就是深入理解数据库索引的全部内容了,谢谢你阅读到了这里!

Author:zhaoyh