前几天我写了点 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谷歌浏览器】打开并收藏！

移动流量偶尔打不开，可以切换电信、联通网络。

收藏网址：www.ziyungong.cc

(＞人＜；)