[CONF] Apache Labs > Algorithms

[confluence]

Algorithms Page edited by Emmanuel Lécharny Changes (1) ... h2. findPos This 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. ... Full Content Let's describe the algorithms we will implement. h1 BTree methods Insert void insert(K, V) Delete V delete(K) Find 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) Browse cursor<V> browse(K) Page methods 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. int findPos(K) Page.findPos(key) : (K) -> int 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 max else if key == keys[max] then return - (max + 1) else return max + 1 There is a small improvment 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. 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