b树和b+树

b树

这是在blog迁移后，将原blog的部分文章重新进行迁移。回头看以前写的东西，很多原来写的东西都变得理所当然，无需赘言;也有很多幼稚的错误,读起来感觉很傻。

btree的特点

btree最大的特点在于是一个绝对平衡的多路搜索树。能够保证所有叶子节点在同一层。同时由于每层的节点很多，所以树的深度很小。能够保证即使btree的下层节点不在内存里，也可以在最短的跳跃后找到。
btree能够保证这个特性的方法就是在保证树的度数超过阈值后，采用分裂的方法，而不是继续向下插入。

这个方法的具体描述就是。btree中对所有非根节点的所含的数据数量有这样一个要求，最少不能少于t-1,最大不能超过2t-1。根节点可以少于t-1但不能超过2t-1。t >=2
插入的时候一旦要超过这个数量，就把树分裂。删除的时候一旦要少于这个数量，要么从兄弟节点借一个节点来充数，如果兄弟节点也不够，就把子树合并。
这样，保证了btree节点最多数据的时候数据的数是一个奇数。因为2t-1==2(t-1)+1，所以一个满节点可以分裂成一个至少有一个数据的根，外加2个最小的节点。

多说无益，上代码

#!/usr/bin/env python
from random import randint,choice
from bisect import 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 BtreeNode(object):
    def __init__(self,t,parent=None):
        if not isinstance(t,int):
            raise InitError,'degree of Btree must be int type'
        if t<2:
            raise InitError,'degree of Btree must be equal or greater then 2'
        else:
            self.vlist=[]
            self.clist=[]
            self.parent=parent
            self.__degree=t
    @property
    def degree(self):
        return self.__degree
    def isleaf(self):
        return len(self.clist)==0
    def traversal(self):
        result=[]
        def get_value(n):
            if n.clist==[]:
                result.extend(n.vlist)
            else:
                for i,v in enumerate(n.vlist):
                    get_value(n.clist[i])
                    result.append(v)
                get_value(n.clist[-1])
        get_value(self)
        return result
    def show(self):
        q=deque()
        h=0
        q.append([self,h])
        while True:
            try:
                w,hei=q.popleft()
            except IndexError:
                return
            else:
                print [v.key for v in w.vlist],'the height is',hei
                if w.clist==[]:
                    continue
                else:
                    if hei==h:
                        h+=1
                    q.extend([[v,h] for v in w.clist])
    def getmax(self):
        n=self
        while not n.isleaf():
            n=n.clist[-1]
        return (n.vlist[-1],n)
    def getmin(self):
        n=self
        while not n.isleaf():
            n=n.clist[0]
        return (n.vlist[0],n)
class IndexFile(object):
    def __init__(fname,cellsize):
        f=open(fname,'wb')
        f.close()
        self.name=fname
        self.cellsize=cellsize
    def write_obj(obj,pos):
           pass
    def read_obj(obj,pos):
        pass
class Btree(object):
    def __init__(self,t):
        self.__degree=t
        self.__root=BtreeNode(t)
    @property
    def degree(self):
        return self.__degree
    def traversal(self):
        """
        use dfs to search a btree's node
        """
        return self.__root.traversal()
    def show(self):
        """
        use bfs to show a btree's node and its height
        """
        return self.__root.show()
    def search(self,mi=None,ma=None):
        """
        search key-value pair within range mi<=key<=ma.
        if mi or ma is not specified,the searching range
        is key>=mi or key <=ma
        """
        result=[]
        node=self.__root
        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_node(n):
            if mi is None:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<=ma:
                            result.extend(n.clist[i].traversal())
                            result.append(v)
                        else:
                            search_node(n.clist[i])
                            return
                    search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if v<=ma:
                            result.append(v)
                        else:
                            break
            elif ma is None:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<mi:
                            continue
                        else:
                            search_node(n.clist[i])
                            while i<len(n.vlist):
                                result.append(n.vlist[i])
                                result.extend(n.clist[i+1].traversal())
                                i+=1
                            break
                    if v.key<mi:
                        search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if v>=mi:
                            result.append(v)
            else:
                if not n.isleaf():
                    for i,v in enumerate(n.vlist):
                        if v<mi:
                            continue
                        elif mi<=v<=ma:
                            search_node(n.clist[i])
                            result.append(v)
                        elif v>ma:
                            search_node(n.clist[i])
                    if v<=ma:
                        search_node(n.clist[-1])
                else:
                    for v in n.vlist:
                        if mi<=v<=ma:
                            result.append(v)
                        elif v>ma:
                            break
        search_node(node)
        return result
    def insert(self,key_value):
        node=self.__root
        full=self.degree*2-1
        mid=full/2+1
        def split(n):
            new_node=BtreeNode(self.degree,parent=n.parent)
            new_node.vlist=n.vlist[mid:]
            new_node.clist=n.clist[mid:]
            for c in new_node.clist:
                c.parent=new_node
            if n.parent is None:
                newroot=BtreeNode(self.degree)
                newroot.vlist=[n.vlist[mid-1]]
                newroot.clist=[n,new_node]
                n.parent=new_node.parent=newroot
                self.__root=newroot
            else:
                i=n.parent.clist.index(n)
                n.parent.vlist.insert(i,n.vlist[mid-1])
                n.parent.clist.insert(i+1,new_node)
            n.vlist=n.vlist[:mid-1]
            n.clist=n.clist[:mid]
            return n.parent
        def insert_node(n):
            if len(n.vlist)==full:
                insert_node(split(n))
            else:
                if n.vlist==[]:
                    n.vlist.append(key_value)
                else:
                    if n.isleaf():
                        p=bisect_left(n.vlist,key_value)  #locate insert point in ordered list vlist
                        n.vlist.insert(p,key_value)
                    else:
                        p=bisect_left(n.vlist,key_value)
                        insert_node(n.clist[p])
        insert_node(node)
    def delete(self,key_value):
        node=self.__root
        mini=self.degree-1
        def merge(n,i):
            n.clist[i].vlist=n.clist[i].vlist+[n.vlist[i]]+n.clist[i+1].vlist
            n.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist
            n.clist.remove(n.clist[i+1])
            n.vlist.remove(n.vlist[i])
            if n.vlist==[]:
                n.clist[0].parent=None
                self.__root=n.clist[0]
                del n
                return self.__root
            else:
                return n
        def tran_l2r(n,i):
            left_max,left_node=n.clist[i].getmax()
            right_min,right_node=n.clist[i+1].getmin()
            right_node.vlist.insert(0,n.vlist[i])
            del_node(n.clist[i],left_max)
            n.vlist[i]=left_max
        def tran_r2l(n,i):
            left_max,left_node=n.clist[i].getmax()
            right_min,right_node=n.clist[i+1].getmin()
            left_node.vlist.append(n.vlist[i])
            del_node(n.clist[i+1],right_min)
            n.vlist[i]=right_min
        def del_node(n,kv):
            p=bisect_left(n.vlist,kv)
            if not n.isleaf():
                if p==len(n.vlist):
                    if len(n.clist[-1])>mini:
                        del_node(n.clise[p],kv)
                    elif len(n.clist[p-1])>mini:
                        tran_l2r(n,p-1)
                        del_node(n.clist[-1],kv)
                    else:
                        del_node(merge(n,p-1),kv)
                else:
                    if n.vlist[p]==kv:
                        left_max,left_node=n.clist[i].getmax()
                        if len(n.clist[p].vlist)>mini:
                            del_node(n.clist[p],left_max)
                            n.vlist[p]=left_max
                        else:
                            right_min,right_node=n.clist[i+1].getmin()
                            if len(n.clist[p+1].vlist)>mini:
                                del_node(n.clist[p+1],right_min)
                                n.vlist[p]=right_min
                            else:
                                del_node(merge(n,p),kv)
                    else:
                        if len(n.clist[p].vlist)>mini:
                            del_node(n.clist[p],kv)
                        elif len(n.clist[p+1].vlist)>mini:
                            tran_r2l(n,p)
                            del_node(n.clist[p],kv)
                        else:
                            del_node(merge(n,p),kv)
            else:
                try:
                    pp=n.vlist[p]
                except IndexError:
                    return -1
                else:
                    if pp!=kv:
                        return -1
                    else:
                        n.vlist.remove(kv)
                        return 0
        del_node(node,key_value)
def test():
    mini=50
    maxi=200
    testlist=[]
    for i in range(1,1001):
        key=randint(1,1000)
        #key=i
        value=choice('abcdefg')
        testlist.append(KeyValue(key,value))
    mybtree=Btree(5)
    for x in testlist:
        mybtree.insert(x)
    print 'my btree is:\n'
    mybtree.show()
    #mybtree.delete(testlist[0])
    #print '\n the newtree is:\n'
    #mybtree.show()
    print '\nnow we are searching item between %d and %d\n\n'%(mini,maxi)
    print [v.key for v in mybtree.search(mini,maxi)]
    #for x in mybtree.traversal():
    #    print x
if __name__=='__main__':
    test()

b+树

在之前，我一直只把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<=3:
            raise InitError,'M must be greater then 3'
        else:
            self.__M=M
            self.clist=[]
            self.ilist=[]
            self.par=None
    def isleaf(self):
        return False
    def isfull(self):
        return len(self.ilist)>=self.M-1
    def isempty(self):
        return len(self.ilist)<=(self.M+1)/2-1
    @property
    def M(self):
        return self.__M
class Bptree_Leaf(object):
    def __init__(self,L):
        if not isinstance(L,int):
            raise InitError,'L must be int'
        else:
            self.__L=L
            self.vlist=[]
            self.bro=None
            self.par=None
    def isleaf(self):
        return True
    def isfull(self):
        return len(self.vlist)>self.L
    def isempty(self):
        return len(self.vlist)<=(self.L+1)/2
    @property
    def L(self):
        return self.__L
class Bptree(object):
    def __init__(self,M,L):
        if L>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 to 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<=ma:
                        result.append(kv)
                    else:
                        return result
                if leaf.bro==None:
                    return result
                else:
                    leaf=leaf.bro
        elif ma is None:
            index,leaf=search_key(node,mi)
            result.extend(leaf.vlist[index:])
            while True:
                if leaf.bro==None:
                    return result
                else:
                    leaf=leaf.bro
                    result.extend(leaf.vlist)
        else:
            if mi==ma:
                i,l=search_key(node,mi)
                try:
                    if l.vlist[i]==mi:
                        result.append(l.vlist[i])
                        return result
                    else:
                        return result
                except IndexError:
                    return result
            else:
                i1,l1=search_key(node,mi)
                i2,l2=search_key(node,ma)
                if l1 is l2:
                    if i1==i2:
                        return result
                    else:
                        result.extend(l.vlist[i1:i2])
                        return result
                else:
                    result.extend(l1.vlist[i1:])
                    l=l1
                    while True:
                        if l.bro==l2:
                            result.extend(l2.vlist[:i2+1])
                            return result
                        else:
                            result.extend(l.bro.vlist)
                            l=l.bro
    def traversal(self):
        result=[]
        l=self.__leaf
        while True:
            result.extend(l.vlist)
            if l.bro==None:
                return result
            else:
                l=l.bro
    def show(self):
        print 'this b+tree is:\n'
        q=deque()
        h=0
        q.append([self.__root,h])
        while True:
            try:
                w,hei=q.popleft()
            except IndexError:
                return
            else:
                if not w.isleaf():
                    print w.ilist,'the height is',hei
                    if hei==h:
                        h+=1
                    q.extend([[i,h] for i in w.clist])
                else:
                    print [v.key for v in w.vlist],'the leaf is,',hei

    def delete(self,key_value):
        def merge(n,i):
            if n.clist[i].isleaf():
                n.clist[i].vlist=n.clist[i].vlist+n.clist[i+1].vlist
                n.clist[i].bro=n.clist[i+1].bro
            else:
                n.clist[i].ilist=n.clist[i].ilist+[n.ilist[i]]+n.clist[i+1].ilist
                n.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist
            n.clist.remove(n.clist[i+1])
            n.ilist.remove(n.ilist[i])
            if n.ilist==[]:
                n.clist[0].par=None
                self.__root=n.clist[0]
                del n
                return self.__root
            else:
                return n
        def tran_l2r(n,i):
            if not n.clist[i].isleaf():
                n.clist[i+1].clist.insert(0,n.clist[i].clist[-1])
                n.clist[i].clist[-1].par=n.clist[i+1]
                n.clist[i+1].ilist.insert(0,n.ilist[i])
                n.ilist[i]=n.clist[i].ilist[-1]
                n.clist[i].clist.pop()
                n.clist[i].ilist.pop()
            else:
                n.clist[i+1].vlist.insert(0,n.clist[i].vlist[-1])
                n.clist[i].vlist.pop()
                n.ilist[i]=n.clist[i+1].vlist[0].key
        def tran_r2l(n,i):
            if not n.clist[i].isleaf():
                n.clist[i].clist.append(n.clist[i+1].clist[0])
                n.clist[i+1].clist[0].par=n.clist[i]
                n.clist[i].ilist.append(n.ilist[i])
                n.ilist[i]=n.clist[i+1].ilist[0]
                n.clist[i+1].clist.remove(n.clist[i+1].clist[0])
                n.clist[i+1].ilist.remove(n.clist[i+1].ilist[0])
            else:
                n.clist[i].vlist.append(n.clist[i+1].vlist[0])
                n.clist[i+1].vlist.remove(n.clist[i+1].vlist[0])
                n.ilist[i]=n.clist[i+1].vlist[0].key
        def del_node(n,kv):
            if not n.isleaf():
                p=bisect_right(n.ilist,kv)
                if p==len(n.ilist):
                    if not n.clist[p].isempty():
                        return del_node(n.clist[p],kv)
                    elif not n.clist[p-1].isempty():
                        tran_l2r(n,p-1)
                        return del_node(n.clist[p],kv)
                    else:
                        return del_node(merge(n,p),kv)
                else:
                    if not n.clist[p].isempty():
                        return del_node(n.clist[p],kv)
                    elif not n.clist[p+1].isempty():
                        tran_r2l(n,p)
                        return del_node(n.clist[p],kv)
                    else:
                        return del_node(merge(n,p),kv)
            else:
                p=bisect_left(n.vlist,kv)
                try:
                    pp=n.vlist[p]
                except IndexError:
                    return -1
                else:
                    if pp!=kv:
                        return -1
                    else:
                        n.vlist.remove(kv)
                        return 0
        del_node(self.__root,key_value)
def test():
    mini=2
    maxi=60
    testlist=[]
    for i in range(1,10):
        key=i
        value=i
        testlist.append(KeyValue(key,value))
    mybptree=Bptree(4,4)
    for kv in testlist:
        mybptree.insert(kv)
    mybptree.delete(testlist[0])
    mybptree.show()
    print '\nkey of this b+tree is \n'
    print [kv.key for kv in mybptree.traversal()]
    #print [kv.key for kv in mybptree.search(mini,maxi)]
if __name__=='__main__':
    test()

总结

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

• 内节点不存储key-value，只存放key
• 沿着内节点搜索的时候，查到索引相等的数要向树的右边走。所以二分查找要选择bisect_right
• 在叶子节点满的时候，并不是先分裂再插入而是先插入再分裂。因为b+tree无法保证分裂的两个节点的大小都是相等的。在奇数大小的数据分裂的时候右边的子节点会比左边的大。如果先分裂再插入无法保证插入的节点一定会插在数量更少的子节点上，满足节点数量平衡的条件。
• 在删除数据的时候，b+tree的左右子节点借数据的方式比btree更加简单有效，只把子节点的子树直接剪切过来，再把索引变一下就行了，而且叶子节点的兄弟指针也不用动。