数据库mysql

Mysql索引的底层数据结构和算法分析

2019-11-29  本文已影响0人  qinghaihu

今天给大家带来的是数据库优化方面的知识.作为java开发工程师,跟数据库打交道是不可避免的,扎实的数据库优化知识也是核心竞争力之一.谈到数据库优化,我想大家肯定听说过慢查询,当然第一个想到的肯定是建索引,或者是建合适的索引,那么为什么建立索引就可以有效的解决查询速度慢的问题呢?联合索引的最左匹配原则它的底层机理又是怎样的呢?索引越多性能就越优异吗?我相信,今天的索引底层数据结构和算法分析会给大家一个更加深入的认识.
MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同.总的来说,MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱和讲述方便，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。
索引（Index）,帮助数据库高效获取数据的一种数据结构.数据查询作为数据库最为核心的功能之一,相信数据库工程师们必定会想方设法的研究数据结构和查询算法来提高数据查询性能.
数据结构那么多，mysql索引为什么要用B+Tree数据结构，而不是其他呢？当然,肯定是其它的数据不满足数据库的要求.

常见的用于查询的数据结构

  1. 二叉查找树
  2. 红黑树
  3. hash
  4. B-Tree
  5. B+Tree

二叉查找树

二叉树.png

左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针.
然而,当我们的索引键值数据是一个单调变化的数据时,我们就会发现,进行查找最糟糕的情况将是O(n)复杂度.

红黑树

红黑树也是二叉查找树的变种,在二叉查找树的基础上,增加了如下约束:

1.节点非红即黑。
2.根节点是黑色。
3.所有NULL结点称为叶子节点，且认为颜色为黑。
4.所有红节点的子节点都为黑色。
5.从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

当键值数据为有序序列时,比如对Col1建立索引,得到的数据结构如下图


红黑树.png

红黑树的深度h与数据量n的关系是

n>=2^h-1

当生产环境达到千万级数据量时,此时红黑树的深度大约为23.这就意味着,最糟糕时,数据库要进行23次磁盘IO,才能找到想要的数据.显然我们是接受不了的.

B-Tree

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。相对于二叉，B树每个内结点有多个分支，即多叉.顺便提一下,B树又可以写成B-树/B-Tree，并不是B“减”树，横杠仅为连接符，容易被误导.
m 阶B-Tree,是指该树一个节点能拥有的最大子节点数为m.B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

3阶B-Tree.png

大家可以看出，B-Tree由于是多叉树，同一层能保存更多的数据，因此它相比于红黑树，会显得矮胖得多。对同样数量的数据进行索引，最恶劣情况，所需要的磁盘IO也会更小一些。

B+Tree

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构。
从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

这里带着大家估算一下一个B+Tree能对多大的数据量进行索引。在mysql数据库中，每个节点（即一个页）的大小为16KB（没有设计的更大，也是出于性能的考虑，过大会导致一个节点io耗时过长)。键值和指针是成对出现的，在实际设计中，我们大多数情况会将主键定义为int型，这里以最大的BigInteger为例，8个字节。mysql数据库，对指针会以6个字节存储（不理解的可以私下微信交流）。也就是一堆键值和指针是14个字节。一个节点可以对16KB/14B=1170个数据进行检索。那么建立一个深度为h的B+Tree树，就可以对1170^(h-1)行数据进行索引了。一亿万的数据量，深度为多少呢？答案是4层。是不是很惊人，就是这么优异。

B+Tree相对于B-Tree有几点不同：

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个链指针。 有助于实现范围查找。
  3. 数据记录都存放在叶子节点中。

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：


3阶B+Tree.png

不同的存储引擎，可能都是基于B+Tree数据结构，但细节上还是有差异的。这里以用的最多的MyISAM和Innodb为例，跟大家深入介绍下。

MyISAM存储引擎下的索引

下图是给出了一个Linux系统下mysql数据库的文件系统。housemagagerAliyun数据库下，test_myisam表采用的MyISAM存储引擎，其它大部分表采用的是Innodb引擎。

mysql数据库.png
mysql文件系统.png
我们可以看到，MyISAM存储引擎会对每张表建立三个文件，分别为sdi、MYD和MYI。其中sdi文件用于存储表的元数据信息，MYD存储的是数据信息，而MYI则是索引信息。
为什么是这样一种结果呢，原来，MyISAM引擎的索引B+Tree的叶子节点仅仅保存的是数据行的地址，数据另外单独存放。
MyISAM index.png

Innodb存储引擎下的索引

上文介绍myisam存储引擎，有贴出innodb表的文件系统，我们可以发现，每个表只有一个ibd文件。由于博主采用的是共享表空间，表的元数据信息是统一放在了上级目录的ibdata1文件中。但你们肯定会想到，那索引和数据呢？难道是放在一个文件里了？答案就在innodb的索引数据结构里了。
innodb的主键索引B+Tree，叶子节点存放着完整的数据记录。


innodb primary index.png

这就是大家在看其它数据库书籍时，介绍的所谓聚集索引概念。而MyISAM的那种，没有保存完整数据记录的，就是非聚集索引了。
而innodb的其它非主键索引，叶子节点存储的数据其实是对应记录行的主键值。也就是非主键索引进行搜索时，其实是需要2次索引的。


secondary index.png
问题来了，为什么mysql会这样设计索引数据结构呢？两点好处
  1. 数据一致性
  2. 节约空间

节约空间很容易理解，那数据一致性怎么理解呢？当你要插入一条新的数据记录时，如果非主键索引也要储存完整的数据，这就意味着，你要同时完成多份数据的修改，这就好比分布式事务一样，要想保证多份数据的一致性，代价是非常高的。但是仅仅在主键索引上保存完整数据，你就可以很容易保证数据一致性了。

联合索引

现有一张mysql职员信息表，定义如下，我们在departmentId,position,和entryDate三个字段上建立联合索引，其索引结构如图所示。

CREATE TABLE `staff_info` (
  `id` int(11) NOT NULL,
  `sex` char(1) NOT NULL,
  `departmentId` int(11) NOT NULL,
  `position` varchar(20) NOT NULL,
  `entryDate` date NOT NULL,
  `exitDate` date NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_union` (`departmentId`,`position`,`entryDate`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (1, 'M', 1002, 'Staff', '1996-08-03', '2002-06-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (2, 'M', 1001, 'Engineer', '1996-08-03', '2001-08-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (3, 'W', 1001, 'Staff', '2001-09-03', '2006-03-06');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (4, 'M', 1003, 'Staff', '1997-08-03', '2011-08-07');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (5, 'W', 1003, 'Staff', '2001-09-03', '2009-06-03');
INSERT INTO `staff_info`(`id`, `sex`, `departmentId`, `position`, `entryDate`, `exitDate`) VALUES (6, 'M', 1004, 'Staff', '1996-08-03', '2010-09-20');

联合索引使用时，必须遵循最左匹配原则，即匹配条件必须有最左列，否则索引将失效。我们利用Explain执行计划对这一原则做一个演示。

  1. 检索条件同时包含联合索引的全字段
mysql>EXPLAIN select  * from staff_info where departmentId = 1002 and position = 'Staff' and entryDate > '1990-01-01';
全匹配索引.png

key列显示，该查询使用了联合索引idx_union，而key_len 69(departmentId(int 4)+position(varchar 3*20+2)+entryDate(date 3))则意味着3列全部用到。69

  1. 检索条件仅为最左第一列
EXPLAIN select  * from staff_info where departmentId = 1002;
union first.png

可以看到，该查询使用了联合索引，索引长度为4(departmentId(int 4))
3.检索条件为联合索引的第二列

EXPLAIN select  * from staff_info where position = 'Staff'
union second.png

type =ALL，执行计划显示，该查询会进行全表扫描，联合索引失效。
这时，你肯定会问，那为什么必须遵循最左匹配原则呢？我们可以从联合索引的底层数据结构中找到答案。


联合索引数据结构.png

我们可以清楚地看到，联合索引的B+Tree每个非叶子节点，是根据最左列编排的，然后再依据其它列进行排序。如果我们的检索条件不包含最左列，这就违背了B+Tree数据结构的设计理念，没法进行高效搜索。

上一篇下一篇

猜你喜欢

热点阅读