bplustreelong.py

R树与B树的混合树

        allocated = this.freeHeadSeek
        this.freeHeadSeek = this.parseFreeBuffer(allocated)
        return allocated
    def parseFreeBuffer(this, buffernumber):
        freesize = 1+BufferFile.LONGSTORAGE
        buffer = this.buffers.getBuffer(buffernumber, freesize)
        indicator = ord(buffer[0])
        if indicator!=FREE:
            raise BplusTreeException, "free buffer not marked free "+repr(buffernumber)
        return BufferFile.RetrieveLong(buffer, 1)
    def deallocateBuffer(this, buffernumber):
        #freesize = 1+BufferFile.LONGSTORAGE
        buffer = this.buffers.getBuffer(buffernumber, 1)
        #print "<br>     DEALLOCATING", buffernumber, "<br>"
        if ord(buffer)==FREE:
            raise BplusTreeException, "attempt to free buffer marked free already"
        buffer = chr(FREE)+BufferFile.StoreLong(this.freeHeadSeek)
        this.buffers.setBuffer(buffernumber, buffer)
        this.freeHeadSeek = buffernumber
    def setHeader(this):
        header = this.makeHeader()
        this.fromfile.seek(this.seekStart)
        this.fromfile.write(header)
    def RecordTerminalNode(this, terminalNode):
        if terminalNode is this.root:
            return # never record root
        if this.TerminalNodeToId.has_key(terminalNode):
            return # don't record twice
        id = this.TerminalNodeCount
        this.TerminalNodeCount = id+1
        this.TerminalNodeToId[terminalNode] = id
        this.IdToTerminalNode[id] = terminalNode
    def ForgetTerminalNode(this, nonterminalNode):
        if not this.TerminalNodeToId.has_key(nonterminalNode):
            return # silently ignore
        id = this.TerminalNodeToId[nonterminalNode]
        del this.TerminalNodeToId[nonterminalNode]
        del this.IdToTerminalNode[id]
    def ShrinkFootprint(this):
        this.InvalidateTerminalNodes(this.FifoLimit)
    def InvalidateTerminalNodes(this, toLimit):
        t2i = this.TerminalNodeToId
        i2t = this.IdToTerminalNode
        while len(i2t)>toLimit:
            # find oldest nonterminal and clear it
            lowcount = this.LowerTerminalNodeCount
            hicount = this.TerminalNodeCount
            while not i2t.has_key(lowcount):
                lowcount+=1
                if (lowcount>hicount):
                    raise BplusTreeException, "error counting terminal nodes"
            this.LowerTerminalNodeCount = lowcount
            victim = i2t[lowcount]
            del i2t[lowcount]
            del t2i[victim]
            if victim.MyBufferNumber!=NULLBUFFERNUMBER:
                victim.Invalidate(True)
    def readHeader(this):
        f = this.fromfile
        f.seek(this.seekStart)
        header = f.read(this.headersize)
        index = len(HEADERPREFIX)
        prefix = header[:index]
        if prefix!=HEADERPREFIX:
            raise BplusTreeException, "bad prefix %s should be %s"%(repr(header[:index]),repr(HEADERPREFIX))
        index+=1 # skip version
        this.NodeSize = BufferFile.RetrieveInt(header, index)
        index+=BufferFile.INTSTORAGE
        this.KeyLength = BufferFile.RetrieveInt(header, index)
        index+=BufferFile.INTSTORAGE
        CultureId = BufferFile.RetrieveInt(header, index)
        index+=BufferFile.INTSTORAGE
        this.rootSeek = BufferFile.RetrieveLong(header, index)
        index+=BufferFile.LONGSTORAGE
        this.freeHeadSeek = BufferFile.RetrieveLong(header, index)
        this.SanityCheck()
    def makeHeader(this):
        result = [HEADERPREFIX]
        result.append(chr(VERSION))
        result.append(BufferFile.StoreInt(this.NodeSize))
        result.append(BufferFile.StoreInt(this.KeyLength))
        result.append(BufferFile.StoreInt(INVARIANTCULTUREID))
        result.append(BufferFile.StoreLong(this.rootSeek))
        result.append(BufferFile.StoreLong(this.freeHeadSeek))
        return string.join(result, "")

class BplusNode:
    isLeaf = True
    Dirty = True
    parent = None
    owner = None
    MyBufferNumber = NULLBUFFERNUMBER
    indexInParent = None
    def __init__(this, owner, parent, indexInParent, isLeaf):
        this.isLeaf = isLeaf
        this.owner = owner
        this.parent = parent
        this.Size = owner.NodeSize
        this.Dirty = True
        this.Clear()
        if parent!=None and indexInParent>=0:
            this.parent.MaterializedChildNodes[indexInParent] = this
            this.MyBufferNumber = this.parent.ChildBufferNumbers[indexInParent]
            this.indexInParent = indexInParent
    def FirstChild(this):
        result = this.MaterializeNodeAtIndex(0)
        if result is None:
            raise BplusTreeException, "no first child"
        return result
    def makeRoot(this):
        p = this.parent
        i = this.indexInParent
        if (p is not None and i is not None):
            p.MaterializedChildNodes[i] = None
        this.parent = None
        this.indexInParent = None
        if (this.MyBufferNumber==NULLBUFFERNUMBER):
            raise BplusTreeException, "no seek allocated to new root"
        return this.MyBufferNumber
    def Free(this):
        #print "<br>freeing", this.MyBufferNumber, "<br>"
        mb = this.MyBufferNumber
        if (mb!=NULLBUFFERNUMBER):
            freeOnAbort = this.owner.FreeBuffersOnAbort
            if freeOnAbort.has_key(mb):
                # free it now
                del this.owner.FreeBuffersOnAbort[mb]
                this.owner.deallocateBuffer(mb)
            else:
                # free on commit
                this.owner.FreeBuffersOnCommit[mb] = mb
        this.MyBufferNumber = NULLBUFFERNUMBER
        #print "<br>nonrecursive destroy for free<br>"
        this.Destroy(False)
    def SanityCheck(this, visited):
        size = this.Size
        if this.ChildKeys is None:
            raise BplusTreeException, "cannot sanity check destroyed node "+repr(id(this))
        if len(this.ChildKeys)!=this.Size:
            raise BplusTreeException, "wrong size child key list"
        if len(this.ChildBufferNumbers)!=this.Size+1:
            raise BplusTreeException, "wrong number of buffer numbers"
        if len(this.MaterializedChildNodes)!=this.Size+1:
            raise BplusTreeException, "wrong number of child nodes"
        result = None
        if visited is None:
            visited = {}
        if visited.has_key(this):
            raise BplusTreeException, "node visited twice "+this.MyBufferNumber
        visited[this] = this
        mb = this.MyBufferNumber
        if visited.has_key(mb):
            raise BplusTreeException, "buffer number seen twice "+`mb`
        visited[mb] = mb
        p = this.parent
        i = this.indexInParent
        if p!=None and i is not None:
            if p.isLeaf:
                raise BplusTreeException, "parent is leaf"
            n = this.parent.MaterializeNodeAtIndex(this.indexInParent)
            if n is not this:
                raise BplusTreeException, "incorrect location in parent"
            # check that half the keys are in use
            limit = this.Size/2-1
            for i in range(limit):
                if this.ChildKeys[i] is None:
                    raise BplusTreeException, "None child in first half of non-root"
        result = this.ChildKeys[0] # for leaf
        if not this.isLeaf:
            firstchild = this.MaterializeNodeAtIndex(0)
            result = firstchild.SanityCheck(visited)
            for i in range(this.Size):
                thekey = this.ChildKeys[i]
                if thekey is None:
                    break
                i1 = i+1
                n = this.MaterializeNodeAtIndex(i1)
                least = n.SanityCheck(visited)
                if least is None:
                    raise BplusTreeException, "None least in child"
                if least!=thekey:
                    raise BplusTreeException, "least in child doesn't match key in node: "+repr((least,thekey))
        # check structure
        keys = this.ChildKeys
        nums = this.ChildBufferNumbers
        kids = this.MaterializedChildNodes
        for i in range(size):
            if keys[i] is not None:
                if nums[i]==NULLBUFFERNUMBER:
                    raise BplusTreeException, "non-null key with null seek at %s" % i
                if not this.isLeaf and nums[i+1]==NULLBUFFERNUMBER:
                    raise BplusTreeException, "non-null key with null greater seek in non leaf at %s" %i
            else:
                if this.isLeaf and kids[i]!=None:
                    raise BplusTreeException, "null key with non-null node at %s"% i
                if kids[i+1]!=None:
                    raise BplusTreeException, "null key with non-null greater node at %s"% i
                if this.isLeaf and nums[i]!=NULLBUFFERNUMBER:
                    raise BplusTreeException, "null key with non-null seek at %s" % i
                if nums[i+1]!=NULLBUFFERNUMBER:
                    raise BplusTreeException, "null key with non-null greater seek at %s" % i
        return result
    def Destroy(this, recursive=True):
        "break all links, make object unusable, it should no longer be used"
        # destroy all materialized kids
        #print "<br>DESTROYING NODE FOR", this.MyBufferNumber, id(this)
        #if this.owner.committing: raise "stopping here for debug"
        kids = this.MaterializedChildNodes
        if recursive and kids is not None:
            for n in kids:
                if n is not None:
                    n.Destroy()
        p = this.parent
        this.MaterializedChildNodes = None
        this.ChildKeys = None
        this.ChildBufferNumbers = None
        this.MyBufferNumber = NULLBUFFERNUMBER
        this.parent = None
        this.owner = None
    def SizeInUse(this):
        result = 0
        size = this.Size
        keys = this.ChildKeys
        while result<size and keys[result] is not None:
            result+=1
        return result
    def Reparent(this, newParent, ParentIndex):
        if ParentIndex<0 or ParentIndex is None:
            raise BplusTreeException, "parent index cannot be none or negative "+repr(ParentIndex)
        this.parent = newParent
        this.indexInParent = ParentIndex
        newParent.ChildBufferNumbers[ParentIndex] = this.MyBufferNumber
        newParent.MaterializedChildNodes[ParentIndex] = this
        this.owner.ForgetTerminalNode(newParent) # parent is no longer terminal (if it was)
    def Clear(this):
        s = this.Size
        s1 = this.Size+1
        this.ChildBufferNumbers = [NULLBUFFERNUMBER]*s1
        this.ChildKeys = [None]*s
        this.MaterializedChildNodes = [None]*s1
        this.owner.RecordTerminalNode(this)
    def FindAtOrNextPosition(this, CompareKey, LookPastOnly):
        "look for lowest index in self associated with same or greater key"
        insertposition = 0
        size = this.Size
        kids = this.ChildKeys
        if (this.isLeaf and not LookPastOnly):
            # look for exact match or greater
            while (insertposition<size and kids[insertposition] is not None
                   and kids[insertposition]<CompareKey):
                insertposition+=1
        else:
            # look for greater
            while (insertposition<size and kids[insertposition] is not None
                   and kids[insertposition]<=CompareKey):
                insertposition+=1
        return insertposition
    def TraverseToFollowingKey(this, atIndex):
        """
        Find the first key below atIndex, or if no such node traverse to the next key to the right.
        If no such key exists, return None.
        Otherwise return (leaf, keyfound)
        """
        FoundInLeaf = None
        KeyFound = None
        LookInParent = False
        size = this.Size
        kids = this.ChildKeys
        #print atIndex, this.ChildKeys
        if (this.isLeaf):