[CONF] Apache Labs > Algorithms

[confluence]

Algorithms Page edited by Emmanuel Lécharny Changes (10) ... h1. BTree methods h1. Insert h2. insert() method When we try to insert a tuple <K, V> into a tree, we start from the root page, which can be either a Leaf or a Node. In any case, we call the insert(K, V) method on the BTree, which will get a new revision that will become the new root if the insertion succeed. ... {code} h1. Delete h2. delete() method TO BE DONE {code:title=V delete(K)|borderStyle=solid} {code} h1. Find h2. find() method This method is used to find a specific value, given a key. ... {code} h1. Browse h2. browse() method {code:title=cursor<V> browse(K)|borderStyle=solid} {code} h1. Page methods h2. Node.insert The 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 : {code} 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 {code} The _BTree_ will deal with a root being split, creating a new root. The _Leaf_ class will deal with the addition of a new value 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 : {code:title=InsertResult<K, V> insert( long, K, V )|borderStyle=solid} 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) {code} This helper method is used to replace a child in a node: {code:title=InsertResult<K, V> replaceChild( long, InsertResult<K, V>, int )|borderStyle=solid} 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 {code} This helper method is used to insert a child in a node: {code:title=InsertResult<K, V> insertChild( long, K, Page<K, V>, Page<K, V>, int )|borderStyle=solid} 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 {code} This helper method is used to create the split pages : {code:title=InsertResult<K, V> addAndSplit( long, K, Page<K, V>, Page<K, V>, int )|borderStyle=solid} 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 ) {code} h2. Leaf.insert This method is terminal (it won't go down one level like the same method in the Node class), as we are now to insert the value in the page. We have three cases to deal with here : # The key already exists in the page # The key does not exist but can be added in the page # The key does not exist and the page is full Let's see what it means for each case # We just have to copy the page, changing its revision, replace the value, and reference the previous and next links. We also return the modified page and the old value # This is a bit more complex : we have to insert the key and the value at the right place in a copy of the page, then we will change the revision, and update the references to the previous and next pages # Even more complex : the page will be split, a new pivot will be computed and send back to the caller. Here is the algorithm : {code:title=InsertResult<K, V> insert( long, K, V )|borderStyle=solid} Leaf.insert(revision, key, value) : (long, K, V) -> InsertResult<K, V> pos <- findPos(key) if pos < 0 // The key is present in the page, case 1 then index <- -(pos + 1) return replaceElement(revision, key, value, index) else if nbElems < BTree.pageSize then // The page is not full, case 2 return addElement(revision, key, value, pos) else // The page is full, case 3 return page.addAndSplit(revision, key, value, pos) {code} This helper method is used to implement the first case : {code:title=InsertResult<K, V> replaceElement(long, K, V, int)|borderStyle=solid} Leaf.replaceElement(revision, key, value, pos) : (long, K, V, int) -> InsertResult<K, V> newLeaf <- new Leaf( btree, revision, nbElems ); copy keys[0..nbElems] to newLeaf.keys[0..nbElems] copy values[0..nbElems] to newLeaf.values[0..nbElems] oldValue <- newLeaf.values[index] newLeaf.values[index] <- value newLeaf.prev <- this.prev newLeaf.next <- this.next InsertResult<K, V> result <- new ModifyResult() result.modifiedValue = oldValue result.modifiedPage = newLeaf return result {code} This helper class is used to manage the case 2 : {code:title=InsertResult<K, V> addElement(long, K, V, int)|borderStyle=solid} Leaf.addElement(revision, key, value, pos) : (long, K, V, int) -> InsertResult<K, V> newLeaf <- new Leaf( btree, revision, nbElems + 1 ); copy keys[0..pos] to newLeaf.keys[0..pos] newLeaf.keys[pos] <- key copy keys[pos..nbElems] to newLeaf.keys[pos+1..nbElems+1] copy values[0..pos] to newLeaf.values[0..pos] newLeaf.values[pos] <- value copy values[pos..nbElems] to newLeaf.values[pos+1..nbElems+1] newLeaf.prev <- this.prev newLeaf.next <- this.next InsertResult<K, V> result <- new ModifyResult() result.modifiedValue = null result.modifiedPage = newLeaf return result {code} This helper method is used to create the split pages : {code:title=InsertResult<K, V> addAndSplit( long, K, V, int )|borderStyle=solid} Leaf.addAndSplit(revision, key, value, pos) : (long, K, V, int) -> InsertResult<K, V> middle <- nbPageSize / 2 leftPage <- null rightPage <- null if pos <= middle then // Create the left page leftPage <- new Leaf(btree, revision, middle + 1) copy keys[0..pos] to leftPage.keys[0..pos] leftPage.keys[pos] <- key copy keys[pos..middle] to leftPage.keys[pos+1..middle+1] copy values[0..pos] to leftPage.values[0..pos] leftPage.values[pos] <- value copy values[pos..middle] to leftPage.values[pos+1..middle+1] // create the right page rightPage <- new Leaf(btree, revision, middle) copy keys[middle..nbElems] to rightPage.keys[0..middle] copy values[middle..nbElems] to rightPage.values[0..middle] else // create the left page leftPage <- new Leaf(btree, revision, middle) copy keys[0..middle] to leftPage.keys[0..middle] copy values[0..middle] to leftPage.values[0..middle] // Create the right page rightPage <- new Leaf(btree, revision, middle + 1) copy keys[middle..pos] to rightPage.keys[0..pos] rightPage.keys[pos] <- key copy keys[pos..nbElems] to rightPage.keys[pos+1..middle+1] copy values[middle..pos] to rightPage.values[0..pos] rightPage.values[pos] <- value copy values[pos..nbElems] to rightPage.values[pos+1..middle+1] // Update the links leftPage.prev <- this.prev leftPage.next <- rightPag rightPage.prev <- leftPage rightPage.next <- this.next // Get the new pivot from the right page newPivot <- rightPage.keys[0] // create the result InsertResult<K, V> result <- new SplitResult() result.newPivot <- newPivot result.leftPage <- leftPage result.rightPage <- rightPage return result {code} h2. AbstractPage.findPos This method is used to find the position of a key in the keys. If the key is found, we will return its position as a negative value. Otherwise, we will return the position of the key which is immediately above the key we are looking for, or the latest position in the page if the new key is higher than any existing keys. We try to make the minimal number of comparisons while searching for the key, as it's a costly operation. If we have a tree with 1 million of elements, and pages containing 16 elements, with pages 66% full, then we will have to go down 6 levels, with around 4 comparisons per page, so around 24 comparisons for each find. {code:title=int findPos(K)|borderStyle=solid} Page.findPos(key) : (K) -> int if nbElems == 0 then return 0 min <- 0 max <- nbElems - 1 while max > min do middle <- ( max + min + 1) / 2 if key == keys[middle] then return - (middle + 1) if key > keys[middle] then min <- middle + 1 else max <- middle - 1 done if key < keys[max] then return min else if key == keys[max] then return - (max + 1) else return max + 1 {code} There is a small improvement done in this algorithm : as we may find the keys before we have gone down to atomic elements, we can save some comparaison by excluding the element we just compared. Full Content Let's describe the algorithms we will implement. BTree methods insert() method When we try to insert a tuple <K, V> into a tree, we start from the root page, which can be either a Leaf or a Node. In any case, we call the insert(K, V) method on the BTree, which will get a new revision that will become the new root if the insertion succeed. void insert(K, V) BTree.insert(key, value) : (K, V) -> V get new revision return insert(revision, key, value) This internal method will try to insert the tuple in the root page, and depending on the result, will either switch the root page to the newly created page, or to create a new root page containing the pivot if the old root page has been split void insert(revision, K, V) BTree.insert(revision, key, value) : (long, K, V) -> V currentRoot <- get the current root page result <- currentRoot.insert(revision, key, value) oldValue <- null newRoot <- null if result is a modified page then newRoot <- result.modifiedPage oldValue <- result.oldValue else // It's a split page newRoot <- new Node(revision) newRoot.children[0] <- result.getLeftPage newRoot.children[1] <- result.getRightPage newRoot.keys[0] <- result.getPivot roots.put(<revision, newRoot>) currentRoot <- newRoot return oldValue delete() method TO BE DONE V delete(K) find() method This method is used to find a specific value, given a key. We will have to go down the tree up to the leaf that contains the value, if the key is present in the tree. We will work on the latest revision available. V find(K) BTree.find(key) : K -> V return currentRoot.find( key ) browse() method cursor<V> browse(K) Change Notification Preferences View Online | View Changes | Add Comment --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@labs.apache.org For additional commands, e-mail: commits-h...@labs.apache.org