B-树的一点形象但是不恰当的比喻 - Shihira

这段时间看了一下B-树，感觉这里面好像有点故事啊。不知创造B-树的人究竟过了一个怎样的人生。

B树的增添

这是一家互联网公司。公司新招聘进来人了，名字叫A，你不可能让它立刻做管理层吧，所以先把这个新人安排到基层做一线码农。等我看看啊，A同学你是广州分舵 - 移动业务分部 - iOS组的。干了一段时间，这个iOS组的人越来越多了，为了方便管理，公司就把组分开成了两个小组，iOS界面组和iOS业务组，同属移动业务分部，然后调了A到移动业务分部做管理层。A的工作能力不上不下但是喜欢拍马屁。后来A因为所在部门膨胀分裂等原因，所以很荣幸地被升到了广州分舵，最后居然到了董事会。到了董事会就升职到头了？并不，这个公司的官僚玩得溜。董事会膨胀着膨胀着，就会出现一批特别会敛财的人。那帮有钱的人啊，事实上又形成了一个更加有权的大董事会，董事会其他人都得听他们的。这个大董事会形成了之后啊，公司所有人发现，自己居然不多不少又多了一个老板。

这是一棵B-树。一个元素新进来了，放到合适的叶节点下面。如果这个叶节点膨胀得太大了，就分裂开来，分裂点（也就是中间的节点）被调到父节点上面。如果父节点膨胀得大了，就又分裂开来。知道根节点膨胀得大了，就会分裂出新的根，旧的根成为新的根的两个子节点。这成为B-树最重要的特性：每个叶节点的的高度都是一样的。

递归的关键是：膨胀，然后分裂，弹出中间那个。中间那个怎么处置交给父节点决定。

B树的删除

中国有句古话叫做虎毒不食子，没说虎毒不坑爹啊。我们要说的一个世纪好爸爸的故事。就拿B君来说，B君是个败家子，三四十岁人了，都有自己家庭的人了，总是赌博赌到家徒四壁。钱不多了咋办，先找兄弟借啊。兄弟有钱就拜托兄弟转点钱过来。但是这次不同了，B的兄弟说我都已经快没钱周转了，借不了给你了。B君怎么说也是个好爸爸，不想坑儿子，就去坑爹了，从老爸那里套来了钱。老爸也终于有一天没钱了，兄弟借不了，就找爷爷拿钱。按着这样下去，最终到了曾曾曾爷爷没钱了，那么曾曾曾爷爷的老爸呢已经是挂了的，曾曾曾爷爷本人也处于濒死状态了，见到自己儿子又来借钱，曾曾曾爷爷就说：我已经是快要死的人了；这样吧，我这副金牙还值点钱，把我杀了，然后拿这金牙去卖吧。卧槽这么说着就觉得好悲伤……

这是一个B-树。从它那里删除一个不在叶节点的元素都可以转化成：将它跟它左子树的最右端（或者右子树的最左端）交换，然后删掉成为叶子的它。删掉以后平衡，说的就是上面的故事。

叶子节点删到小于最低限度了，这时它可以选择先找兄弟：左兄弟还宽裕，就把左兄弟最右端的元素通过右旋过来（用父节点中转）；左兄弟穷了，但是右兄弟还宽裕，就把右兄弟最左端的元素通过左旋取过来（用父节点中转，说到底还是坑爹）。如果兄弟没有了，才去找父节点，父节点就不用想太多了，直接拿就是了，父节点自己会处理（也就是回到本段的开头，递归开始了）。留意到永远不要去拿子节点的元素。

根节点是唯一一个没有最低限度的（或者说最低就是0），随意拿就是了。一直拿拿到根节点没有元素了，就把根节点删掉。这是B-树唯一高度下降的途径。

真是麻烦又不恰当的比喻。见笑了。B-Tree详细的定义和算法还请翻课本。本文只是为了加深记忆，或者梳理思路用。