B+树

引言

时隔一年,我又想起当初看数据库时,看到的B+树,就是数据库的索引使用的数据结构。再整理一下,看看自己没有忘记很多吧。

概述

B+树之前,先来看一下二叉查找树(1,2,3,4,5,6,7)

img

恩, 差不多就长这样。诚然,在二叉查找树中查找某个元素是很快速的,二分查找嘛。但想想数据库查找数据的场景:

select * from user where id > 10, 显然,对于这种查找区间来说,二叉查找树并不高效。那么B+树是如何解决这个问题的呢?

试想一下,区间查找比较高效的数据结构是什么?数组,只要找到id为10的元素下标,那么之后的所有就都符合了。

那么把上面修改一下,让二叉查找树树的叶子节点直接指向数组的下标不就好了嘛。修改后结构如下:

img

这时,如果想找select * from user where id > 2 and id < 5, 那么,直接找到2的下标,然后向后遍历,到第一个>=5的值出现停止,之间是满足条件的数据。没错,这就是B+树。

这个结构是怎么想出来的我不知道啊,但是我今天突然发现,他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发?亦或是跳表受到了B+树的启发?咱也不知道。

引申

很好,B+树整明白了,新的问题出现了。如果数据库使用这种数据结构存储,全部放到内存中肯定是不现实的,势必要将其存储到硬盘中,待查找时再到文件中读取。但如果放到文件中,势必会造成IO的缓慢,每次读取节点都访问文件,要是树到高度很夸张的话,光IO就要耗尽耐心了。

既然如此,那就降低IO好了,增加树每一层的节点数量,也就是二叉树变成n叉树(也确实是这么做的)。

算一下,如果是3叉树,高度为3(这个高度为索引树的高度),可索引的数组长度为:(3^4=81);如果是5叉树,高度为3,可索引数组长度为:(5^4=625);如果是100叉树,高度为3,可索引长度为:(100^4=1亿)。索引1亿的数据量,高度也只有3,意味着只要进行3此IO就可以定位到。完美。

那树进行分叉过多,是不是在每个节点搜索子节点的效率下降了?这里可以再使用一些查找算法降低时间复杂度。

以上就是我回忆的内容了,感觉并没有什么晦涩的,大部分是重新回忆了一遍。但是,温故而知新嘛。不知点新怎么好意思写出来。一下就是我最近才晓得的了。

B+树是不是分叉越多越好

那肯定不是越多越好啊,要是一层就把所有数据都存储了,要他还有什么用,根本没有起到快速定位的作用。

但我想说的并不是这。我们知道,操作系统在读取磁盘中的数据时,是按照页来读取和管理的,一页大小为4kb。当读取数据时,如果大小超过4kb,就会触发多次IO。4kb的大小,其实对于存储节点已经很大了。也就是说,我们每个节点的大小最好是<=4kb,否则就会触发多次IO。

但是,节点在更新时,势必会导致其大小改变。如何保证n叉树始终为n叉树呢?

添加节点

其实很简单,多了就拆呗。如果节点超出大小,就拆分成两个节点。但拆分后父节点不就多了么。那就父节点在拆,一直拆到根节点为止。如果根节点在超出大小,那就再拆,整个新的根节点出来。

删除节点

其实,删除节点不做处理也不会影响节点大小超出限制。但是,长此以往,可能会导致某些节点元素过少,严重影响查询效率。那么,如果节点内元素的数量小于n/2,就把相邻的两个节点合并为一个节点。那要是合并后元素数量超出大小呢?再拆呗。


原文地址 https://hujingnb.com/archives/282

转载请保留原文连接: B+树 | 烟草的香味

订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x