四时宝库

程序员的知识宝库

Mysql 索引的数据结果(mysql索引详解)

MySQL索引主要有两种结构:B+Tree索引和Hash索引,接下来我们会讲解到Hash表、二叉查找树、平衡二叉树、B树以及B+树。

Hash索引

顾名思义,哈希索引是通过哈希表实现的,只有精确匹配索引所有列的查询才有效,对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(HashCode),并且Hash索引将所有的哈希码存储在索引中,同时在索引表中保存指向每个数据行的指针。



只能用于等值查询,时间复杂度为O(1),但是不支持范围快速查找,范围查找时还是只能通过扫描全表方式。

当出现Hash冲突的时候,存储引擎必须遍历整个链表中的所有行指针,逐行比较,直到找到所有的符合条件的行,若Hash冲突很多的话,其索引维护的代价很高,并且性能并不一定会比BTree索引高。

Hash索引存储的是Hash码而不是键值,所以无法用于排序。如果是需要范围查询数据的,显然这种并不适合。

二叉查找树

如果是按照7,4,9,2,5,8,11的顺序添加节点。那么树的结构图如下:


二叉树的特点:每个节点最多有2个分叉,左子树和右子树数据顺序左小右大。

二叉树的实现主要为了每次查找都可以折半而减少IO次数,但还有种情况下很容易出现树不分叉了,这时候树退化成链表了,如下图:


平衡二叉树

平衡二叉树除了具备二叉树的特点之外,最主要的特征是它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

使用平衡二叉查找树查询时间复杂度是 O(log2n)。查询id=5,只需要两次IO。


平衡二叉树存在的一些问题:

平衡二叉树不支持范围查询快速查找,范围查询时需要从根节点多次遍历,查询效率不高

树有多高就需要检索多少次,每个节点的读取,都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道时间为10ms,在表数据量大时,查询性能就会很差。

B树(B-Tree)

MySQL的数据是存储在磁盘文件中的,查询数据时需要先把磁盘中的数据加载到内存中,磁盘IO操作非常耗时,所以我们优化的重点就是尽量减少磁盘IO操作,所以,我们应当尽量减少从磁盘中读取数据的次数。另外,从磁盘中读取数据时,都是按照磁盘块来读取的,并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中,那一次磁盘读取操作就会读取更多数据,那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么?说明每个磁盘块仅仅存储一个键值和数据!那如果我们要存储海量的数据呢?

可以想象到二叉树的节点将会非常多,高度也会极其高,我们查找数据时也会进行很多次磁盘IO,我们查找数据的效率将会极低!

为了解决平衡二叉树的这个弊端,B树应运而生, B树是一种多叉平衡查找树,主要的特点是:

叶子节点都在同一层,叶子节点没有指针连接

B树的节点中存储着多个元素,每个内节点有多个分叉

节点中的元素包含键值和数据,节点中的键值从大到小排列

下面用一张图对比平衡二叉树和B树:


从中我们可以看出,将二叉树改造成了多叉树,通过增加树的叉树,将树从高瘦变为矮胖,在从磁盘中查找数据(先读取到内存、后查找)的过程中,可以减少磁盘IO的次数,从而提升查找速度。

下面以一张图讲解在B树中查找数据的情况:

相比较二叉平衡查找树,虽然比较的次数没有明显的减少,但是磁盘IO次数大大减少,B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树创建索引可以很好的提升查询的效率。但是在实际的数据库应用中仍存在一些问题无法解决。

B树中每个节点中包含key值以及data值,而每一个节点的存储空间是有限的(MySQL默认16K),如果data中存放的数据较大时,将会导致每个节点能存储的key的数量很小,所以当数据量很多,且每行数据量很大的时候,同样会导致树的高度变得很高,增大查询时的磁盘IO次数,进而影响查询效率。

不支持范围查询的快速查找,而在实际的应用中,数据库范围查询的频率非常高,以下的一种情况是我查找10和35之间的数据,查找到15之后,需要回到根节点重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。

问题总是推动改进的前提,为了解决以上问题,对B-Tree 进行改造优化,进而演变出了B+Tree。

B+树(B+Tree)

对比B树和B+树,我们发现二者主要存在以下几点不同的地方:

数据都存放在叶子节点中

非叶子节点只存储键值信息,不再存储数据

所有叶子节点之间都有一个指针,指向下一个叶子节点,而且叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表

既然B+树解决了B树的范围查询问题,那么接下来我们来看一下等值查询和范围查询。

发表评论:

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言
    友情链接