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

前几天我写了点btree的东西(http://thuhak.blog.51cto.com/2891595/1261783)，今天继续这个思路，继续写b+tree。而且b+tree才是我的目的，更加深入理解文件和数

前几天我写了点btree的东西()，今天继续这个思路，继续写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指针数组所占的磁盘空间完全浪费。

一个数据的大小和硬盘指针的大小取决于key-value中key和value大小的比值。假如说这个比值是2:1。那么btree浪费了几乎1/3的空间。

b+tree针对这个问题的，把叶子节点和内节点的数据结构分开设计，让叶子节点不存放指针。因此同样大小的叶子节点，b+tree所能包含数据数量要比btree大。按照上面的假设就是大1/2。数的深度很可能比btree矮，大范围搜索或遍历所需要的载入磁盘的次数也少。

另外，b+tree还有一个特点是所有数据都存放在叶子节点，这些叶子节点也可以组成一个链表，并把这个链表的表头拿出来，方便直访问数据。有些文章认为这对于范围搜索来说是个巨大的优化。但是就我的看法，这个特性最大的作用仅仅是让代码更容易一些，性能上，只会比树的遍历差，而不会比树的遍历好。因为不管是用指向叶子节点的指针搜，还是用树的遍历搜，所搜索的节点的数量都是几乎相同的。在相同大小的范围搜索的性能，只取决于访问顺序的连续性。从树根向下遍历，那么一次可以取得大量的子节点的范围，并针对这些节点做访问排序，得到更好的访问连续性。如果是沿着指向兄弟节点的指针搜索，一是兄弟节点也许是后插入的，存放并不一定和自己是连续的，二是只有每次从硬盘中将改节点载入到内存，才知道兄弟节点放在硬盘哪个位置，这又变成了对硬盘的一个随机的同步操作，性能的下降可想而知。

说b+tree因为有指向兄弟节点的指针方便数据库扫库这种结论，是不正确的。

还是上代码吧,依旧只是在内存对数据结构插入删除查找的模拟

#!/usr/bin/env python from random import randint,choice from bisect import bisect_right,bisect_left from collections import deque class InitError(Exception): pass class ParaError(Exception): pass class KeyValue(object): __slots__=('key','value') def __init__(self,key,value): self.key=key self.value=value def __str__(self): return str((self.key,self.value)) def __cmp__(self,key): if self.key>key: return 1 elif self.key==key: return 0 else: return -1 class Bptree_InterNode(object): def __init__(self,M): if not isinstance(M,int): raise InitError,'M must be int' if M=self.M-1 def isempty(self): return len(self.ilist)self.L def isempty(self): return len(self.vlist)M: raise InitError,'L must be less or equal then M' else: self.__M=M self.__L=L self.__root=Bptree_Leaf(L) self.__leaf=self.__root @property def M(self): return self.__M @property def L(self): return self.__L def insert(self,key_value): node=self.__root def split_node(n1): mid=self.M/2 newnode=Bptree_InterNode(self.M) newnode.ilist=n1.ilist[mid:] newnode.clist=n1.clist[mid:] newnode.par=n1.par for c in newnode.clist: c.par=newnode if n1.par is None: newroot=Bptree_InterNode(self.M) newroot.ilist=[n1.ilist[mid-1]] newroot.clist=[n1,newnode] n1.par=newnode.par=newroot self.__root=newroot else: i=n1.par.clist.index(n1) n1.par.ilist.insert(i,n1.ilist[mid-1]) n1.par.clist.insert(i+1,newnode) n1.ilist=n1.ilist[:mid-1] n1.clist=n1.clist[:mid] return n1.par def split_leaf(n2): mid=(self.L+1)/2 newleaf=Bptree_Leaf(self.L) newleaf.vlist=n2.vlist[mid:] if n2.par==None: newroot=Bptree_InterNode(self.M) newroot.ilist=[n2.vlist[mid].key] newroot.clist=[n2,newleaf] n2.par=newleaf.par=newroot self.__root=newroot else: i=n2.par.clist.index(n2) n2.par.ilist.insert(i,n2.vlist[mid].key) n2.par.clist.insert(i+1,newleaf) newleaf.par=n2.par n2.vlist=n2.vlist[:mid] n2.bro=newleaf def insert_node(n): if not n.isleaf(): if n.isfull(): insert_node(split_node(n)) else: p=bisect_right(n.ilist,key_value) insert_node(n.clist[p]) else: p=bisect_right(n.vlist,key_value) n.vlist.insert(p,key_value) if n.isfull(): split_leaf(n) else: return insert_node(node) def search(self,mi=None,ma=None): result=[] node=self.__root leaf=self.__leaf if mi is None and ma is None: raise ParaError,'you need setup searching range' elif mi is not None and ma is not None and mi>ma: raise ParaError,'upper bound must be greater or equal than lower bound' def search_key(n,k): if n.isleaf(): p=bisect_left(n.vlist,k) return (p,n) else: p=bisect_right(n.ilist,k) return search_key(n.clist[p],k) if mi is None: while True: for kv in leaf.vlist: if kv

实现过程和btree很像，不过有几点显著不同。

1.内节点不存储key-value，只存放key

2.沿着内节点搜索的时候，香港服务器租用，查到索引相等的数要向树的右边走。所以二分查找要选择bisect_right