Node methodsPage added by Emmanuel LécharnyThis page describes the algorithms implemented for the Node class find() methodThe find method will search in the current Node to see which children it should find for the value. V find(K)
BTree.find(key) : K -> V
pos <- findPos(this, key)if pos < O then return children[-pos].find( key ) else return children[pos].find( key ) insert() methodThe insertion in a Node is slightly more complex than an insertion in a Leaf, as it's a recursive algorithm : as all the values are stored in leaves, we have to go down the whole tree, update the leaf, and go up. In the process, if the leaf is full, we will move one key up to its parent page, which may also be full, etc. At the end, the root page may itself be full. In any case, if the child page was split, then we should insert in the current page the new pivot and if the current page is full, we should split it up, find the new pivot and return it to the caller. We come up with such an algorithm : find the page in which we should insert the new key result <- page.insert(key) if result is a split page then split the current page find the new pivot return <new pivot, left page, right page> else return a copy of the current page The BTree will deal with a root being split, creating a new root. Whatever happens, we will create a new set of pages with new revisions from the top of the tree down to the bottom. There is one more tricky thing to deal with, when we have more than one level : the pivot we push up into the parent must be removed from the page, when it will remain into a Leaf. Here is the full algorithm : InsertResult<K, V> insert( long, K, V ) Node.insert(revision, key, value): (long, V, K) -> InsertResult pos <- this.findPos(this, key) if ( pos < 0 ) // The key has been found in the page then pos <- -( pos + 1 ) result <- this.children[pos].insert(revision, key, value) // Eventually call the Leaf if result is a modifiedResult then return replaceChild( revision, result, pos) else pivot <- result.getPivot() leftPage <- result.getLeftPage() rightPage <- result.getRightPage() if nbElems == maxElems then // Split current page return addAndSplit( revision, pivot, leftPage, rightPage, pos ) else // Insert new child return insertChild(revision, pivot, leftPage, rightPage, pos) replaceChild() methodThis helper method is used to replace a child in a node: InsertResult<K, V> replaceChild( long, InsertResult<K, V>, int ) Leaf.replaceChild(revision, result, pos) : (long, InsertResult<K, V>, int) -> InsertResult<K, V> newNode = copy current node newNode.children[pos] = result.modifiedPage result.modifiedPage = newNode return result insertChild() methodThis helper method is used to insert a child in a node: InsertResult<K, V> insertChild( long, K, Page<K, V>, Page<K, V>, int ) Leaf.insertChild(revision, key, leftPage, rightPage, pos) : (long, K, Page<K, V>, Page<K, V>, int) -> InsertResult<K, V> newNode = new Node(revision, nbElems + 1) // Special case when the page is empty if nbElems == 0 then newNode.keys[0] <- key newNode.children[0] <- leftPage newNode.children[1] <- rightPage else copy this.keys[0..pos] to newNode.keys[0..pos] copy this.children[0..pos] to newNode.children[0..pos] // Insert the key and pages newNode.keys[pos] <- key newNode.children[pos] <- leftPage newNode.children[pos+1] <- rightPage // And copy the remaining elements copy this.keys[pos..nbElems] to newNode.keys[pos+1..nbElems+1] copy this.children[pos+1..nbElems+1] to newNode.children[pos+2..nbElems+2] // create the result InsertResult<K, V> result <- new ModifyResult( newNode, null) return result addAndSplit() methodThis helper method is used to create the split pages : InsertResult<K, V> addAndSplit( long, K, Page<K, V>, Page<K, V>, int ) Leaf.addAndSplit(revision, pivot, leftPage, rightPage, pos) : (long, K, Page<K, V>, Page<K, V>, int) -> InsertResult<K, V> middle <- nbPageSize / 2 // create the new left and right page newLeftPage <- new Leaf(btree, revision, middle) newRightPage <- new Leaf(btree, revision, middle) if pos < middle then // Copy the keys and the children up to the insertion position copy keys[0..pos] to newLeftPage.keys[0..pos] copy children[0..pos] to newLeftPage.children[0..pos] // Add the new element newLeftPage.keys[pos] <- pivot newLeftPage.children[pos] <- leftPage newLeftPage.children[pos+1] <- rightPage // And copy the remaining elements minus the new pivot copy keys[pos..middle] to newLeftPage.keys[pos + 1..middle] copy children[pos + 1..middle] to newLeftPage.children[pos + 2..middle + 1] // create the right page newRightPage <- new Leaf(btree, revision, middle) copy keys[middle-1..nbElems] to newRightPage.keys[0..middle] copy children[middle..nbElems+1] to newRightPage.children[0..middle+1] // Create the result return new SplitResult( keys[middle - 1], newLeftPage, newRightPage ) else if pos == middle then // Copy the keys and the children up to the middle copy keys[0..middle] to newLeftPage.keys[0..middle] copy children[0..middle] to newLeftPage.children[0..middle] // Update the left child newLeftPage.children[middle] = leftPage // process the rightPage now copy keys[middle..nbElems] to newLeftPage.keys[0..middle] copy children[middle + 1..nbElems + 1] to newLeftPage.children[1..middle] // Update the right child newRightPage.children[0] = rightPage // Create the result return new SplitResult( pivot, newLeftPage, newRightPage ) else copy keys[0..middle] to newLeftPage.keys[0..middle] copy children[0..middle+1] to newLeftPage.children[0..middle+1] // Copy the keys and the children in the right page up to the pos copy keys[middle+1..pos] to rightPage.keys[0..pos] copy children[middle..pos] to rightPage.children[0..pos] // Add the new element rightPage.keys[pos - middle - 1] <- pivot rightPage.children[pos - middle - 1] <- leftPage rightPage.children[pos - middle] <- rightPage // And copy the remaining elements minus the new pivot copy keys[pos..nbElems] to rightPage.keys[pos+1..middle+1] copy values[pos..nbElems] to rightPage.values[pos+1..middle+1] // Create the result return new SplitResult( pivot, newLeftPage, newRightPage )
Change Notification Preferences
View Online
|
Add Comment
|
