问:数据库中最常见的慢查询优化方式是什么?
同学A:加索引。
问:为什么加索引能优化慢查询?
同学A:...不知道同学B:因为索引其实就是一种优化查询的数据结构,比如Mysql中的索引是用B+树实现的,而B+树就是一种数据结构,可以优化查询速度,可以利用索引快速查找数据,所以能优化查询。
问:你知道哪些数据结构可以提高查询速度?
同学B:哈希表、完全平衡二叉树、B树、B+树等等。
问:那这些数据结构既然都能优化查询速度,那Mysql种为何选择使用B+树?
同学B:...不知道
问:为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询,为何Mysql独独喜欢B+树?
哈希表有什么特点?
假如有这么一张表(表名:sanguo):
现在对name字段建立哈希索引:
注意字段值所对应的数组下标是哈希算法随机算出来的,所以可能出现哈希冲突。那么对于这样一个索引结构,现在来执行下面的sql语句:
select*fromsanguowherename='周瑜'
可以直接对‘周瑜’按哈希算法算出来一个数组下标,然后可以直接从数据中取出数据并拿到锁对应那一行数据的地址,进而查询那一行数据。 那么如果现在执行下面的sql语句:
select*fromsanguowherename>'周瑜'
则无能为力,因为哈希表的特点就是可以快速的精确查询,但是不支持范围查询。
如果用完全平衡二叉树呢?
还是上面的表数据用完全平衡二叉树表示如下图(为了简单,数据对应的地址就不画在图中了。):
图中的每一个节点实际上应该有四部分:
另外需要提醒的是,二叉树是有顺序的,简单的说就是“左边的小于右边的”假如我们现在来查找‘周瑜’,需要找2次(第一次曹操,第二次周瑜),比哈希表要多一次。而且由于完全平衡二叉树是有序的,所以也是支持范围查找的。
如果用B树呢?
还是上面的表数据用B树表示如下图(为了简单,数据对应的地址就不画在图中了。):
可以发现同样的元素,B树的表示要比完全平衡二叉树要“矮”,原因在于B树中的一个节点可以存储多个元素。
如果用B+树呢?
还是上面的表数据用B+树表示如下图(为了简单,数据对应的地址就不画在图中了。):
我们可以发现同样的元素,B+树的表示要比B树要“胖”,原因在于B+树中的非叶子节点会冗余一份在叶子节点中,并且叶子节点之间用指针相连。
那么B+树到底有什么优势呢?
这里我们用“反证法”,假如我们现在就用完全平衡二叉树作为索引的数据结构,我们来看一下有什么不妥的地方。实际上,索引也是很“大”的,因为索引也是存储元素的,我们的一个表的数据行数越多,那么对应的索引文件其实也是会很大的,实际上也是需要存储在磁盘中的,而不能全部都放在内存中,所以我们在考虑选用哪种数据结构时,我们可以换一个角度思考,哪个数据结构更适合从磁盘中读取数据,或者哪个数据结构能够提高磁盘的IO效率。回头看一下完全平衡二叉树,当我们需要查询“张飞”时,需要以下步骤
同理,回头看一下B树,我们发现只发送三次磁盘IO就可以找到“张飞”了,这就是B树的优点:一个节点可以存储多个元素,相对于完全平衡二叉树所以整棵树的高度就降低了,磁盘IO效率提高了。
而B+树是B树的升级版,只是把非叶子节点冗余一下,这么做的好处是为了提高范围查找的效率。
到这里可以总结出来,Mysql选用B+树这种数据结构作为索引,可以提高查询索引时的磁盘IO效率,并且可以提高范围查询的效率,并且B+树里的元素也是有序的。
转载自:https://blog.csdn.net/zl1zl2zl3/article/details/88321108