bplustreelong.py

R树与B树的混合树

        return (RightLeastKey, DeleteRight)
    def DeleteLeaf(this, key):
        "delete key, return (new least, mergeMe)"
        result = None
        MergeMe = False
        found = False
        deletelocation = 0
        for thiskey in this.ChildKeys:
            if thiskey is None:
                break
            if thiskey==key:
                found = True
                break
            deletelocation+=1
        if not found:
            #print this.toHtml()
            raise BplusTreeKeyMissing, "key not found for delete "+repr(key)
        this.Soil()
        #print "deleteposition from leaf", this.toHtml()
        this.DeletePosition(deletelocation)
        if this.SizeInUse()<this.Size/2:
            MergeMe = True
        if deletelocation==0:
            result = this.ChildKeys[0]
            if result is None:
                result = key # signal empty leaf
        return (result, MergeMe)
    def Insert(this, key, value):
        "insert key in subtree, returns (new least, splitString, SplitNode)"
        size = this.Size
        splitString = None
        SplitNode = None
        result = None
        insertposition = this.FindAtOrNextPosition(key, False)
        #dosplit = False
        keys = this.ChildKeys
        kids = this.MaterializedChildNodes
        numbers = this.ChildBufferNumbers
        if this.isLeaf:
            # if exact match then just replace the value
            if insertposition<size and keys[insertposition]==key:
                # replace value for existing key
                numbers[insertposition] = value
            else:
                # insert of new key
                keys.insert(insertposition, key)
                numbers.insert(insertposition, value)
                if keys[-1] is not None:
                    # do split
                    SplitNode = BplusNode(this.owner, this.parent, None, this.isLeaf)
                    nkeys = len(keys)
                    splitpoint = nkeys/2
                    splitlength = nkeys-splitpoint
                    splitString = keys[splitpoint]
                    myFreeSpace = size - splitpoint
                    splitFreeSpace = size - splitlength
                    this.ChildKeys = keys[:splitpoint] + [None]*myFreeSpace
                    this.ChildBufferNumbers = numbers[:splitpoint] + [NULLBUFFERNUMBER]*(myFreeSpace+1)
                    SplitNode.ChildKeys = keys[splitpoint:] + [None]*splitFreeSpace
                    SplitNode.ChildBufferNumbers = numbers[splitpoint:] + [NULLBUFFERNUMBER]*splitFreeSpace
                    SplitNode.DumpToFreshBuffer()
                    SplitNode.Soil()
                    this.owner.RecordTerminalNode(SplitNode)
                else:
                    # no split needed just delete end elements
                    del keys[-1]
                    del numbers[-1]
            if insertposition==0:
                result = key
        else:
            # insert into nonleaf
            InsertChild = this.MaterializeNodeAtIndex(insertposition)
            (childInsert, childSplitString, childSplit) = InsertChild.Insert(key, value)
            if insertposition==0:
                result = childInsert # new least, maybe
            if childSplit is not None:
                #print "<h1>for %s inserting child into</h1>" % repr(childSplitString)
                #print this.toHtml()
                # handle split of child
                this.Soil() # redundant
                newChildPosition = insertposition+1
                keys.insert(insertposition, childSplitString)
                numbers.insert(newChildPosition, childSplit.MyBufferNumber)
                kids.insert(newChildPosition, childSplit)
                childSplit.Reparent(this, newChildPosition)
                #print "<h1>after insert</h1>"
                #print this.toHtml()
                # split this node if needed
                if keys[-1] is None:
                    # no split needed, just delete extra entries
                    del keys[-1]
                    del numbers[-1]
                    del kids[-1]
                else:
                    # split this
                    #print "<h1>this to split</h1>"
                    #print this.toHtml()
                    nkeys = len(keys)
                    splitposition = int(nkeys/2)
                    SplitNode = BplusNode(this.owner, this.parent, None, this.isLeaf)
                    splitString = keys[splitposition]
                    myFreeSpace = size-splitposition
                    splitFreeSpace = size-(nkeys-splitposition)+1
                    this.ChildKeys = keys[:splitposition]+[None]*myFreeSpace
                    SplitNode.ChildKeys = keys[splitposition+1:]+[None]*splitFreeSpace
                    this.MaterializedChildNodes = kids[:splitposition+1]+[None]*myFreeSpace
                    SplitNode.MaterializedChildNodes = kids[splitposition+1:]+[None]*splitFreeSpace
                    this.ChildBufferNumbers = numbers[:splitposition+1]+[NULLBUFFERNUMBER]*myFreeSpace
                    SplitNode.ChildBufferNumbers = numbers[splitposition+1:]+[NULLBUFFERNUMBER]*splitFreeSpace
                    SplitNode.DumpToFreshBuffer()
                    SplitNode.Soil()
                    SplitNode.ReparentAllChildren()
                    this.owner.RecordTerminalNode(SplitNode)
                    #print "<h1>split this</h1>"
                    #print this.toHtml()
                    #print "<h1>split remainder</h1>"
                    #print SplitNode.toHtml()
            this.ReparentAllChildren()
        this.Soil()
        return (result, splitString, SplitNode)
    def Load(this, buffer):
        this.Clear()
        indicator = ord(buffer[0])
        this.isLeaf = (indicator==LEAF)
        if indicator not in NONFREE:
            raise BplusTreeException, "can't parse buffer not marked non-free"
        index = 1
        this.ChildBufferNumbers[0] = BufferFile.RetrieveLong(buffer, index)
        index+=BufferFile.LONGSTORAGE
        maxLength = this.owner.KeyLength
        maxKeyPayload = maxLength - BufferFile.SHORTSTORAGE
        lastkey = ""
        keys = this.ChildKeys
        numbers = this.ChildBufferNumbers
        for KeyIndex in xrange(this.Size):
            KeyLength = BufferFile.RetrieveShort(buffer,index)
            index+=BufferFile.SHORTSTORAGE
            key = None
            if (KeyLength==0):
                key = ""
            elif (KeyLength>0):
                section = buffer[index:index+KeyLength]
                (key, nchars) = DECODER(section)
            keys[KeyIndex] = key
            index+= maxKeyPayload
            seekPosition = BufferFile.RetrieveLong(buffer, index)
            numbers[KeyIndex+1] = seekPosition
            index+= BufferFile.LONGSTORAGE
    def Dump(this):
        L = []
        a = L.append
        if this.isLeaf:
            a(chr(LEAF))
        else:
            a(chr(NONLEAF))
        keys = this.ChildKeys
        numbers = this.ChildBufferNumbers
        #print "<br>keys", keys
        #print "<br>numbers", numbers, "<br>"
        maxLength = this.owner.KeyLength
        maxKeyPayload = maxLength - BufferFile.SHORTSTORAGE
        a(BufferFile.StoreLong(numbers[0]))
        for KeyIndex in xrange(this.Size):
            # store the key
            theKey = keys[KeyIndex]
            if theKey is None:
                a(BufferFile.StoreShort(-1))
                a("X"*maxKeyPayload)
            else:
                (coded, nchars) = ENCODER(theKey)
                lcoded = len(coded)
                if (lcoded>maxKeyPayload):
                    raise BplusTreeException, "too many bytes in key "+repr(coded)
                a(BufferFile.StoreShort(lcoded))
                padded = coded + "X"*(maxKeyPayload-lcoded)
                a(padded)
            # store the seek
            a(BufferFile.StoreLong(numbers[KeyIndex+1]))
        result = string.join(L, "")
        #print "<br>", this.MyBufferNumber, "raw dump", repr(result), "<br>"
        return result
    def Invalidate(this, destroyRoot=True):
        result = this.MyBufferNumber
        if not this.isLeaf:
            # invalidate all kids
            m = this.MaterializedChildNodes
            n = this.ChildBufferNumbers
            for i in range(len(m)):
                kid = m[i]
                if kid is not None:
                    n[i] = kid.Invalidate(True)
                m[i] = None
        if (this.Dirty):
            result = this.DumpToFreshBuffer();
        this.owner.ForgetTerminalNode(this)
        p = this.parent
        ip = this.indexInParent
        if (p is not None and ip is not None):
            p.MaterializedChildNodes[ip] = None
            p.ChildBufferNumbers[ip] = result # redundant
            p.CheckIfTerminal()
        this.indexInParent = None
        this.parent = None
        if (destroyRoot):
            #print "<br>destroying invalidated node", result, id(this)
            this.Destroy()
        return result
    def Soil(this):
        "mark this and all ancestors dirty"
        if this.Dirty:
            return
        this.Dirty = True
        p = this.parent
        if p is not None:
            p.Soil()
    def CheckIfTerminal(this):
        if not this.isLeaf:
            for n in this.MaterializedChildNodes:
                if n is not None:
                    this.owner.ForgetTerminalNode(this)
                    return
        this.owner.RecordTerminalNode(this)
    def AsHtml(this, L=None, mapLong=None):
        if L is None: L=[]
        if this.ChildKeys is None:
            L.append("<BR>DESTROYED NODE<BR>\n")
            return L
        hygeine = "clean"
        if (this.Dirty): hygeine = "dirty"
        keycount = 0
        if this.isLeaf:
            for i in xrange(len(this.ChildKeys)):
                key = this.ChildKeys[i]
                seek = this.ChildBufferNumbers[i]
                if mapLong is not None:
                    seek = mapLong(seek)
                if key is not None:
                    L.append("%s. %s : %s<br>\n" %(keycount, repr(key), seek))#repr(key)+" : "+repr(seek)+"<br>\n")
                    keycount+=1
            L.append("leaf "+`this.indexInParent`+" at "+`this.MyBufferNumber`+
                     " #keys="+`keycount`+" "+hygeine+"\r\n")
        else:
            L.append("<table border>\r\n")
            L.append("<tr><td colspan=2>nonleaf %s at %s hygeine %s</td></tr>" %
                     (this.indexInParent, this.MyBufferNumber, hygeine))
            for i in xrange(len(this.ChildKeys)+1):
                seek = this.ChildBufferNumbers[i]
                if seek!=NULLBUFFERNUMBER:
                    node = this.MaterializeNodeAtIndex(i)
                    L.append("<tr><td align=right valign=top>%s(%s)</td><td>"%(i,seek))
                    node.AsHtml(L)
                    L.append("</td></tr>")
                if i<this.Size:
                    key = this.ChildKeys[i]
                    if key is not None:
                        L.append("<tr><td>%s: %s</td><td></td></tr>" %(keycount, key))
                keycount+=1
            L.append("<tr><td colspan=2>nkeys = %s</td></tr></table>" %this.SizeInUse())
        return L
    def toHtml(this, mapLong=None):
        return string.join(this.AsHtml(mapLong=mapLong), "\n")

def BinaryRoot(LeftNode, key, RightNode, owner):
    newRoot = BplusNode(owner, None, None, False)
    newRoot.ChildKeys[0] = key
    LeftNode.Reparent(newRoot, 0)
    RightNode.Reparent(newRoot, 1)
    return newRoot