电脑版
首页

搜索 繁体

11 关于 B+tree (附 python 模拟代码)

热门小说推荐

最近更新小说

前几天我写了点 btree 的东西(/2891595/1261783),今天继续这个思路,继续写 b+tree。

而且 b+tree 才是我的目的,更加深入理解文件和数据库索引的基本原理。

在之前,我一直只把 b+tree 当成是 btree 的一种变形,或者说是在某种情况下的一种优化,另外一些情况可能还是 btree 好些。但是做完之后才发现,b+tree 在各种情况都可以完全取代 btree,并能够让索引性能得到比 btree 更好的优化。因为 b+tree 设计的核心要点,是为了弥补 btree 最大的缺陷。

btree 最大的缺陷是什么?

首先,我们知道对于 btree 和 b+tree 这种多路搜索树来说,一个很重要的特点就是树的度数非常大。因为只有这样才能够降低树的深度,减少磁盘读取的次数。而树的度数越大,叶子节点在树中的比例就越大。假设度数为 1000,那么叶子节点比他上一层内部节点的数量至少要多 1000 倍,在上一层就更加可以忽略不计了。可以说树种 99.9% 的节点都是叶子节点。 但是对于 btree 来说,所有节点都是一样的结构,都含有一定数量的数据和指向节点的指针。这两项数据占据 btree 节点的几乎全部的空间。一个节点内的数据的数量比硬盘指针的数量少一,可以说和指针的数量几乎相等。对于 python 这种动态类型语言感觉不出来,但是对于 C 这种固定类型语言来说,即使这个 children list 数组为空,这个数组的空间也都是预留出去的。导致的结果就是占绝大多数的叶子节点的 children list 指针数组所占的磁盘空间完全浪费。

Loading...

未加载完,尝试【刷新】or【退出阅读模式】or【关闭广告屏蔽】。

尝试更换【Firefox浏览器】or【Chrome谷歌浏览器】打开多多收藏!

移动流量偶尔打不开,可以切换电信、联通、Wifi。

收藏网址:www.ziyungong.cc

(>人<;)