[CONF] Apache Labs > Leaf methods

[confluence]

Leaf methods Page edited by Emmanuel Lécharny Changes (1) ... return result {code} h2. delete() method Deleting an element from a leaf is pretty simple : we just have to find its position, and if found, to copy the page, and to remove the element from it. The problem is that doing so may result in a leaf with less than N/2 elements, which is not allowed for a leaf, except if it's the root page. So we have to either add an element into the page to make it contains N/2 elements, or to merge it with a page that contains N/2 elements. Then if we merge two pages, we will have to remove an element in the parent page, with the exact same consequences. At the end, the whole tree may be impacted. Here, we can't really distinguish the algorithm used to delete an element from a _Leaf_ from the one applied on a _Node_. We will study the global algorithm, and then describe the specific algorithms for a _Leaf_ and for a _Node_. h3. General algorithm There are a few cases we should consider : # The page is a _Leaf_ but is also the root page : simply remove the element # The page has more than N/2 elements : ## The element is on the left : remove it and return the next element to the parent, as the parent's key will change. ## The element is on the middle of the page : simply remove it # The page has exactly N/2 elements ## There is a sibling with more than N/2 elements ### The sibling has the same parent : borrow the element from it (and update the parent accordingly if we get the element from the right sibling ### The sibling has a different parent : update the parent's sibling up to the page which does not have the moved key on its left ## Both siblings have N/2 elements : select the sibling which has the same parent page, and merge it with the current page. This is the most complex case, as the resulting parent's page may contain less than N/2 elements, and we have to recursively apply the same algorithm. If we reach the root, which has only one element, then we will have to remove the root page and use the merged pages as the new root. Let's see how it translates using some pseudo-code {code} delete( key ) : K -> DeleteResult<K, V> {code} Full Content This page describes the algorithms implemented in the Leaf class. find() method This method is used to find a specific value, given a key. We just have to check in the current page if the key is present, and if so, to return the associated value, otherwise we return null. V find(K) find(key) : K -> V pos = findPos( key ) if pos < 0 then return values[ - ( pos + 1 ) ] else return null insert() method 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 : InsertResult<K, V> insert( long, K, V ) 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) This helper method is used to implement the first case : InsertResult<K, V> replaceElement(long, K, V, int) 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 This helper class is used to manage the case 2 : InsertResult<K, V> addElement(long, K, V, int) 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 This helper method is used to create the split pages : InsertResult<K, V> addAndSplit( long, K, V, int ) 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 delete() method Deleting an element from a leaf is pretty simple : we just have to find its position, and if found, to copy the page, and to remove the element from it. The problem is that doing so may result in a leaf with less than N/2 elements, which is not allowed for a leaf, except if it's the root page. So we have to either add an element into the page to make it contains N/2 elements, or to merge it with a page that contains N/2 elements. Then if we merge two pages, we will have to remove an element in the parent page, with the exact same consequences. At the end, the whole tree may be impacted. Here, we can't really distinguish the algorithm used to delete an element from a Leaf from the one applied on a Node. We will study the global algorithm, and then describe the specific algorithms for a Leaf and for a Node. General algorithm There are a few cases we should consider : The page is a Leaf but is also the root page : simply remove the element The page has more than N/2 elements : The element is on the left : remove it and return the next element to the parent, as the parent's key will change. The element is on the middle of the page : simply remove it The page has exactly N/2 elements There is a sibling with more than N/2 elements The sibling has the same parent : borrow the element from it (and update the parent accordingly if we get the element from the right sibling The sibling has a different parent : update the parent's sibling up to the page which does not have the moved key on its left Both siblings have N/2 elements : select the sibling which has the same parent page, and merge it with the current page. This is the most complex case, as the resulting parent's page may contain less than N/2 elements, and we have to recursively apply the same algorithm. If we reach the root, which has only one element, then we will have to remove the root page and use the merged pages as the new root. Let's see how it translates using some pseudo-code delete( key ) : K -> DeleteResult<K, V> 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