前言

B+树(B Plus Tree)是MySQL数据库索引的底层数据结构,B+树也是一种平衡树和AVL树以及红黑树有着同样的性能,不用你说,我知道你肯定又个疑问,为什么数据库要使用B+树作为数据库索引而不是其他平衡树呢?为什么需要使用B+树呢?或许看完这篇文章你应该就懂了。

其他结构的问题

数据库索引作为数据库中的重要组成部分,同时也是数据库性能的重要指标,数据库是索引必须拥有较好的性能,这包括执行效率(时间)和内存消耗(空间),在执行效率方面,我们希望通过索引,查询数据的效率尽可能的高;在存储空间方面,我们希望索引不要消耗太多的内存空间。

在以上的需求下,支持快速增删改查的数据结构除了B/B+树大概还有以下几种:

  • 哈希表(Hash Table)
  • 跳表(Skip List)
  • 二叉搜索树(Binary Search Tree)
  • 红黑树(Red-Black Tree)
  • 平衡二叉树(AVL Tree)

首先看下哈希表,哈希表拥有O(1)的增删改查的性能,乍一看似乎是最适合作为数据库索引的数据结构。但是,数据库索引不止能等值索引还需要支持范围索引,而哈希表并不能提供范围索引的功能,所以哈希表不能胜任。

接着是跳表,跳表之前的文章介绍过了,这里就直接说它的理由吧,跳表的空间复杂度是O(nlogn)相比其他平衡结构差,而数据库需要应对的是大量的数据,需要大量的内存和磁盘空间,所以一般不采用跳表作为数据库索引的数据结构。

二叉搜索树在极端条件下会退化成链表,造成数据库性能不稳定的情况,而其他平衡树拥有更稳定的性能,所以不会使用二叉搜索树。

AVL树都是一种极为成熟的平衡树结构,维护AVL树的平衡是非常耗时的,AVL树适合用于插入删除次数比较少,但查找多的情况。而数据库有可能进行频繁的插入删除操作,所以不适合。

红黑树似乎是和B/B+树一样适合作为数据库索引的,但是为什么MySQL不使用红黑树而是采用B+树呢?首先红黑树并不太适合范围查找,还有其他的就在下面说明吧。

B+树

B+树是什么样子的呢?

首先为了支持范围查找,二叉树需要进行一些小改造:把数据都移到叶节点中,上层树结构只存储下层的索引。思路类似于跳表,但是上层索引使用的是树结构而不是链表结构。

除了执行效率和内存消耗的考虑,数据库索引还需要考虑其他一些东西:在海量的数据中索引应该存在哪?有些同学可能会说内存啊,但是内存真的能存下海量的数据索引吗?假如我们要存储10亿个字段,每个索引12B则叶节点大概需要11G,整个索引树内存占用不大于20G。20G对于一台服务器已经是不小的压力了,所以,为了节省内存,如果把树存储在硬盘中,那么每个节点的读取(或者访问),都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。而磁盘IO操作又极为耗时,所以为了减少磁盘IO操作则二叉树需要进行改造,将层高减少,即使用N叉树。

这样的结构就可以减少对磁盘IO的操作次数,同时又保留了高效的增删改查效率,而这种结构就是B+树,数据由叶节点的指向,索引中在保留key,节省内存。

这时有人就会问这个N要设置为多少为才是最好的?我们知道磁盘是按一定大小读取数据块的,这个大小是一个固定值,通常是4KB,装系统中常说的4K对齐其实就是设置数据块的大小,为了防止读取一个B+树节点的时候多次操作磁盘,同时最大化的利用每个数据块,B+树的每个节点应尽量充满整个数据块,通过计算就可以得出N的大小。

B+树是如何维持平衡的呢?

说了这么多,那B+树作为一种平衡结构肯定有一种方式来维持平衡,在跳表中是随机高度,在平衡树中一般是采用左右旋的方式维持平衡,那么B+树又是如何呢?

当数据量庞大的时候势必会造成某个节点的大小超过数据块的大小,如何很好的解决这种问题?没错就是分裂,将一个节点分成两份,这样每一份就都小于数据块的大小了,就能保证每次读取一个节点只需要一次磁盘操作了。

那分裂又是如何进行的呢?我们知道叶节点才是存储数据的节点,其他上层节点只存储了key,但叶节点过大的时候节点进行分裂,分裂后数据的位置就不同了,所以还需要更新上层索引,当上层索引过大的时候就需要同叶节点一样分裂,直到分裂到根节点。

删除的时候就和分裂相反,当某个数据删除后节点中的数据数量少于某个特定的阈值的时候(通常是N/2)就需要与兄弟节点进行合并,合并后同样需要更新上层索引,若合并后节点过大的时候就应该同插入一样进行分裂,直到两个节点的大小处于合理的范围之中。

总算更完这篇文章了,溜了溜了。插图看看吧,有空再画 (逃

说点什么
本博客评论规则(评论规则什么的都是浮云,小声
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...