透过B树、B+树来聊聊Mysql索引

Mysql一直都是互联网公司关系型数据库的首选,而索引的使用更是重中之重。然而去年面试过很多人,发现多数人对索引的了解还是很一般。所以很建议大家可以抽些时间来看一下Mysql索引相关的内容,这里推荐《高性能Mysql 第三版》,其中索引的部分讲的非常好。

这里也没打算详细介绍索引,如果以后有机会会单独写一篇文章来介绍Mysql的索引的,不过我觉得上面提到的那本书真的对索引的部分讲的非常简单明了,建议大家可以看看。其实Mysql的InnoDB用了B+树作为索引的数据存储结构,我的《轻松学算法》这本书里也有提到这部分内容。本文就来好好介绍下B树和B+树,以及Mysql索引是如何应用B+树来快速查找的。

B树

B树,很多地方会写B-树,很多人就会以为是B减树,实际上这个“-”是横岗,所以中文翻译过来感觉B树更合适一些,千万别B减树丢人了。B树是一种树型数据结构,用以对数据的存储、排序,并可以以O(logN)的时间进行查找、顺序读取、插入、删除。

对比二叉查找树,B树的一个节点可以拥有多于两个子节点,是一个多路自平衡搜索树。他有以下的特点(对于M路B树来说):

根节点至少有两个节点
每个节点有M-1个关键字,并且升序排列
M-1和M之间的子节点的关键字的值,都在M-1和M关键字值之间(大于等于M-1的值,小于等于M的值)
除根节点外的其他节点至少有M/2个子节点
所有的值会分部再整棵树中,搜索有可能再非叶子节点结束

下面演示往B树中依次插入一下元素的过程(M=4,转载自http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html)

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

B树插入过程演示

B+树

接下来介绍我们的主角B+树,B+树其实和B树很像,但是有一定的变化,主要体现在下面两方面:

所有关键字都存储在叶子节点,非叶节点只存储索引,只有索引功能,
所有叶子节点增加链指针,形成一个链表,可以顺序遍历所有叶节点。

下面先看下B+树的插入演示吧。

B+树插入过程演示

B+树相比B树有什么优点呢?

其实很容易想到,B+树由于所有数据都存储在叶子节点,所以数据更加紧密。另外由于所有叶节点有了指针,所以遍历起来性能很高。

Mysql索引设计

Mysql索引有个顺序使用的规则,有很多人对索引不是很熟悉,或者知道索引只能优先使用前面的部分,不知道为什么。

其实常常面试的时候问到索引,比如想要找出位于北京的所有90后用户列表,怎么设计索引。

先看一下sql会是怎么写的(比如地域,北京对应的是1)
select * from xxx where localId=1 and age<=28

很多人会说给地域加个索引,再给年龄加个索引。这样有用吗?有点用,但是不对。如果单独对两个字段做索引,那么针对这个sql语句,其实只能用到地域这一个索引,年龄是不会走索引的。看了上面B+树的原理,应该很好理解这里的原因。

正确的索引设计应该是做联合索引:KEY(localId,age)。这样如果只需要对地域做查询,可以用到这个索引,两个同时使用也可以用这个索引。但是如果只想对年龄做索引,这个索引是没有办法使用的(因为年龄再不同地域不是连续的)。

联合索引B+树是怎么存储的呢,其实也会做排序,先根据localId进行排序,再根据age进行排序存储。所以我们想直接用age进行索引的话就没法用这个联合索引了。但是想要找到北京的90后,就很容易可以找到。为什么呢,首先可以定位到localId为1的索引部分,接下来找到1岁开始,一直到28岁都拿出来。因为是个链表结构,所以这块的内容可以顺序索引出来而不需要再去重新走索引了。

现在来想一下,如果想找出北京和天津的90后呢?显然有点麻烦,根据B+树的结构,找到北京,然后再去列出年龄范围数据;再去找到天津,再去列出年龄范围数据。所以还是需要找两遍,而没有办法一次就找出来两组数据不是连续的。

举下例子,比如数据叶子节点链表是这样的:

北京,1岁、北京,2岁、北京,3岁、上海,1岁,上海,3岁、天津,2岁,天津3岁。

索引找到北京,找对应年龄范围,而没有办法再通过链表找天津的年龄范围数据了。当地域城市的过滤条件多的话,其实效率就并不高了。

通过这个例子以及B+树的存储结构,大家应该理解联合索引该怎么设计,以及为什么索引的范围查找效率会比较高了。

©原创文章,转载请注明来源: 赵伊凡's Blog
©本文链接地址: 透过B树、B+树来聊聊Mysql索引

发表评论

电子邮件地址不会被公开。 必填项已用*标注