bplustreelong.py

R树与B树的混合树

            LookInParent = (atIndex>=size) or (this.ChildKeys[atIndex] is None)
        else:
            LookInParent = (atIndex>size) or (atIndex>0 and (kids[atIndex-1] is None))
        if LookInParent:
            if this.parent is not None and this.indexInParent is not None:
                return this.parent.TraverseToFollowingKey(this.indexInParent+1)
            # otherwise no such key
        elif this.isLeaf:
            # found
            FoundInLeaf = this
            KeyFound = kids[atIndex]
        else:
            # look in child
            if (atIndex==0 or (kids[atIndex-1] is not None)):
                thechild = this.MaterializeNodeAtIndex(atIndex)
                return thechild.TraverseToFollowingKey(0)
        return (FoundInLeaf, KeyFound)
    def FindMatch(this, CompareKey):
        "find match for key, returning integer or None for not found"
        (leaf, position) = this.FindAtOrNextPositionInLeaf(CompareKey, False)
        if position>=leaf.Size:
            return None
        key = leaf.ChildKeys[position]
        if key==CompareKey:
            ValueFound = leaf.ChildBufferNumbers[position]
            return (ValueFound,)
        return None
    def FindNextKey(this, CompareKey):
        result = None
        (leaf, position) = this.FindAtOrNextPositionInLeaf(CompareKey, True)
        if position>=leaf.Size or leaf.ChildKeys[position] is None:
            (newleaf, result) = leaf.TraverseToFollowingKey(leaf.Size)
        else:
            result = leaf.ChildKeys[position]
        return result
    def FindAtOrNextPositionInLeaf(this, CompareKey, LookPastOnly):
        InLeaf = None
        position = None
        myposition = this.FindAtOrNextPosition(CompareKey, LookPastOnly)
        if (this.isLeaf):
            InLeaf = this
            position = myposition
        else:
            child = this.MaterializeNodeAtIndex(myposition)
            return child.FindAtOrNextPositionInLeaf(CompareKey, LookPastOnly)
        return (InLeaf, position)
    def MaterializeNodeAtIndex(this, myposition):
        if this.isLeaf:
            raise BplusTreeException, "cannot materialize child of leaf"
        childBufferNumber = this.ChildBufferNumbers[myposition]
        if (childBufferNumber==NULLBUFFERNUMBER):
            raise BplusTreeException, "can't materialize None subtree"
        result = this.MaterializedChildNodes[myposition]
        if result is not None:
            return result
        # otherwise read it in
        result = BplusNode(this.owner, this, myposition, True) # dummy isleaf
        result.LoadFromBuffer(childBufferNumber)
        this.MaterializedChildNodes[myposition] = result
        this.owner.ForgetTerminalNode(this)
        return result
    def LoadFromBuffer(this, buffernumber):
        #print "<br>loading", buffernumber, "<br>"
        rawdata = this.owner.buffers.getBuffer(buffernumber)
        #print "<br>raw load", repr(rawdata), "<BR>"
        this.Load(rawdata)
        this.Dirty = False
        this.MyBufferNumber = buffernumber
        this.owner.RecordTerminalNode(this)
    def DumpToFreshBuffer(this):
        oldbuffernumber = this.MyBufferNumber
        freshBufferNumber = this.owner.allocateBuffer()
        this.DumpToBuffer(freshBufferNumber)
        if (oldbuffernumber!=NULLBUFFERNUMBER):
            # eventually free it...
            freeOnAbort = this.owner.FreeBuffersOnAbort
            if freeOnAbort.has_key(oldbuffernumber):
                # free it now
                del freeOnAbort[oldbuffernumber]
                this.owner.deallocateBuffer(oldbuffernumber)
            else:
                # free on commit
                this.owner.FreeBuffersOnCommit[oldbuffernumber] = oldbuffernumber
        this.owner.FreeBuffersOnAbort[freshBufferNumber] = freshBufferNumber
        return freshBufferNumber
    def DumpToBuffer(this, buffernumber):
        rawdata = this.Dump()
        #print "<br>dumping to", buffernumber, "<br>"#, ":", repr(rawdata)
        # debug test: old buffer must be free, never overwrite a non-free buffer
        test = this.owner.buffers.getBuffer(buffernumber, 1)
        if len(test)>0 and ord(test)!=FREE:
            raise BplusTreeException, "overwriting allocated buffer "+repr(buffernumber)+" "+repr(test)
        this.owner.buffers.setBuffer(buffernumber, rawdata)
        this.Dirty = False
        this.MyBufferNumber = buffernumber
        p = this.parent
        ip = this.indexInParent
        if p is not None and ip is not None:
            if (ip>=0 and
                p.MaterializedChildNodes[ip] is not this):
                raise BplusTreeException, "bad parent linkage"
            if (p.ChildBufferNumbers[ip]!=buffernumber):
                p.ChildBufferNumbers[ip] = buffernumber
                p.Soil()
    def ReparentAllChildren(this):
        for i in xrange(this.Size+1):
            n = this.MaterializedChildNodes[i]
            if n is not None:
                n.Reparent(this, i)
    def Delete(this, key):
        "delete key from subtree, return (newleast, mergeme)"
        size = this.Size
        MergeMe = False
        result = None
        if (this.isLeaf):
            return this.DeleteLeaf(key)
        deleteposition = this.FindAtOrNextPosition(key, False)
        DeleteChild = this.MaterializeNodeAtIndex(deleteposition)
        (delresult, MergeKid) = DeleteChild.Delete(key)
        if delresult==key:
            # special case for small nodes: empty leaf
            if (size>3):
                raise BplusTreeException, "empty leaf for too large size"
            if deleteposition==0:
                # new least
                result = this.ChildKeys[0]
            DeleteChild.Free()
            #print "delete for empty leaf", this.toHtml()
            this.DeletePosition(deleteposition-1)
            MergeMe = this.SizeInUse()<this.Size/2
            return (result, MergeMe)
        if (deleteposition==0):
            result = delresult # smallest key may have changed
        elif delresult is not None and deleteposition>0 and delresult!=key:
            this.ChildKeys[deleteposition-1] = delresult
        if MergeKid:
            if deleteposition==0: # merge with previous
                leftindex = deleteposition
                rightindex = deleteposition+1
                leftNode = DeleteChild
                rightNode = this.MaterializeNodeAtIndex(rightindex)
            else: # merge with next
                leftindex = deleteposition-1
                rightindex = deleteposition
                leftNode = this.MaterializeNodeAtIndex(leftindex)
                rightNode = DeleteChild
            keyBetween = this.ChildKeys[leftindex]
            (RightLeastKey, DeleteRight) = this.Merge(leftNode, keyBetween, rightNode)
            if DeleteRight:
                #print "delete right after merge", this.toHtml()
                this.DeletePosition(rightindex-1)
                rightNode.Free()
                if this.SizeInUse()<this.Size/2:
                    MergeMe = True
            else:
                this.ChildKeys[rightindex-1] = RightLeastKey
        return (result, MergeMe)
    def DeletePosition(this, deletePosition):
        #print "<br>deleteposition", deletePosition, "<br>", this.toHtml(), "<br>"
        bns = this.ChildBufferNumbers
        ck = this.ChildKeys
        mc = this.MaterializedChildNodes
        d1 = deletePosition
        if not this.isLeaf:
            d1 = deletePosition+1
            if deletePosition==-1:
                deletePosition = 0
            #print "in nonleaf deleting key at", deletePosition, "from", ck
            #print "deleting node at", d1, "from", bns
        if deletePosition<0:
            raise BplusTreeException, "cannot delete negative position "+repr(deletePosition)
        del ck[deletePosition]
        del bns[d1]
        del mc[d1]
        ck.append(None)
        bns.append(NULLBUFFERNUMBER)
        mc.append(None)
        this.ReparentAllChildren()
        #print "<br>after deleteposition", deletePosition, "<br>", this.toHtml(), "<br>"
    def LeastKey(this):
        result = None
        if this.isLeaf:
            result = this.ChildKeys[0]
        else:
            n = this.MaterializeNodeAtIndex(0)
            result = n.LeastKey()
        if result is None:
            raise BplusTreeException, "no key found"
        return result
    def Merge(this, left, KeyBetween, right):
        "merge left and right: return (rightleast key, delete right flag)"
        size = this.Size
        RightLeastKey = None
        DeleteRight = False
        if left.isLeaf!=right.isLeaf:
            raise BplusTreeException, "cannot merge nodes of differing type"
        leftInUse = left.SizeInUse()
        rightInUse = right.SizeInUse()
        leftKeys = left.ChildKeys[:leftInUse]
        rightKeys = right.ChildKeys[:rightInUse]
        if left.isLeaf:
            # merge leaves
            AllKeys = leftKeys+rightKeys
            leftNodes = left.MaterializedChildNodes[:leftInUse]
            leftNumbers = left.ChildBufferNumbers[:leftInUse]
            rightNodes = right.MaterializedChildNodes[:rightInUse]
            rightNumbers = right.ChildBufferNumbers[:rightInUse]
            allNodes = leftNodes+rightNodes
            allNumbers = leftNumbers+rightNumbers
            supersize = len(AllKeys)
            if supersize<=size:
                DeleteRight = True # fits in one node
                freespace = size-supersize
                freespace1 = freespace+1
                left.ChildKeys = AllKeys + [None]*freespace
                left.ChildBufferNumbers = allNumbers + [NULLBUFFERNUMBER]*freespace1
                left.MaterializedChildNodes = allNodes + [None]*freespace1
                left.ReparentAllChildren()
                left.Soil()
            else: # doesn't fit in one node
                splitposition = supersize/2
                RightLeastKey = AllKeys[splitposition]
                leftfree = size-splitposition
                leftfree1 = leftfree+1
                rightfree = size-(supersize-splitposition)
                rightfree1 = rightfree+1
                left.ChildKeys = AllKeys[:splitposition] + [None]*leftfree
                right.ChildKeys = AllKeys[splitposition:] + [None]*rightfree
                left.MaterializedChildNodes = allNodes[:splitposition] + [None]*leftfree1
                right.MaterializedChildNodes = allNodes[splitposition:] + [None]*rightfree1
                left.ChildBufferNumbers = allNumbers[:splitposition] + [NULLBUFFERNUMBER]*leftfree1
                right.ChildBufferNumbers = allNumbers[splitposition:] + [NULLBUFFERNUMBER]*rightfree1
                left.ReparentAllChildren()
                right.ReparentAllChildren()
                left.Soil()
                right.Soil()
        else:
            # merge non-leaves
            AllKeys = leftKeys+[KeyBetween]+rightKeys
            leftNodes = left.MaterializedChildNodes[:leftInUse+1]
            leftNumbers = left.ChildBufferNumbers[:leftInUse+1]
            rightNodes = right.MaterializedChildNodes[:rightInUse+1]
            rightNumbers = right.ChildBufferNumbers[:rightInUse+1]
            allNodes = leftNodes+rightNodes
            allNumbers = leftNumbers+rightNumbers
            supersize = len(AllKeys)
            if supersize<=size:
                DeleteRight = True # fits in one node
                freespace = size-supersize
                left.ChildKeys = AllKeys + [None]*freespace
                left.ChildBufferNumbers = allNumbers + [NULLBUFFERNUMBER]*freespace
                left.MaterializedChildNodes = allNodes + [None]*freespace
                left.ReparentAllChildren()
                left.Soil()
            else: # doesn't fit in one node
                splitposition = supersize/2
                RightLeastKey = AllKeys[splitposition]
                leftfree = size-splitposition
                rightstart = splitposition+1
                rightfree = size - (supersize-rightstart)
                left.ChildKeys = AllKeys[:splitposition] + [None]*leftfree
                right.ChildKeys = AllKeys[rightstart:] + [None]*rightfree
                left.MaterializedChildNodes = allNodes[:rightstart] + [None]*leftfree
                right.MaterializedChildNodes = allNodes[rightstart:] + [None]*rightfree
                left.ChildBufferNumbers = allNumbers[:rightstart] + [NULLBUFFERNUMBER]*leftfree
                right.ChildBufferNumbers = allNumbers[rightstart:] + [NULLBUFFERNUMBER]*rightfree
                left.ReparentAllChildren()
                right.ReparentAllChildren()
                left.Soil()
                right.Soil()