# eXtremeDB B-Tree Search Algorithm

> The index search algorithm operates with key weights, not with key values, regardless of whether the index direction is `ascending` or `descending`. The search operations and their rules require some explanation. To demonstrate how key searches produce their result sets, consider a simple key containing one integer field populated with the dataset `[1,2,2,3,4,4,5]`.

> Following is a table representing the keys’ values and their respective weights after a search operation is performed:

> Key Value | Key Weight
> --- | ---
> 1 | 0
> 2 | 1
> 2 | 1
> 3 | 2
> 4 | 3
> 4 | 3
> 5 | 4

> Now consider a slightly less trivial example where the key is represented as a structure containing two fields: an integer and a string. The compare function compares integers as in the above sample and the char buffers as ASCII characters. Assume that the dataset is as follows:

>         [ (1,"ZZZ"), (1,"BBB"), (2,"AAA"), (2,"AAA"), (2,"BBB"), (3,"XXX") ]

> The resulting key weight-table is:

> Key Value | Key Weight
> --- | ---
> 1, “BBB” | 0
> 1, “ZZZ” | 1
> 2, “AAA” | 2
> 2, “AAA” | 2
> 2, “BBB” | 3
> 3, “XXX” | 4

> If the index is in the reverse order (declared as `descending`) the weight tables will be as follows:

> Key Value | Key Weight
> --- | ---
> 5 | 0
> 4 | 1
> 4 | 1
> 3 | 2
> 2 | 3
> 2 | 3
> 1 | 4

> Key Value | Key Weight
> --- | ---
> 3, “XXX” | 0
> 2, “BBB” | 1
> 2, “AAA” | 2
> 2, “AAA” | 2
> 1, “ZZZ” | 3
> 1, “BBB” | 4

> For B-Tree indexes, there are five search operations which have internal operation codes: `MCO_LT, MCO_LE, MCO_EQ, MCO_GE`, and `MCO_GT`. A search operation specifies one of these operation codes and the results are returned in a `cursor` positioned to the appropriate element of the index.

> Abbreviating “weight of the specified keys value” as WSKV and “cursor’s current element” as CCE, the following table describes how they are correlated by the eXtremeDB runtime:

> Search operation | Search condition | Description of rules
> --- | --- | ---
> MCO_LT | less than (<) | Points the CCE to the first key with weight WSKV-1
> MCO_LE | less than or equal (<=) | Points the CCE to the last (rightmost) occurrence from the keys with weight equal to WSKV or (if not found) to the first key with weight WSKV-1
> MCO_EQ | equal (==) | Points the CCE to the first (leftmost) key with weight equal to WSKV
> MCO_GE | greater than or equal (>=) | Points the CCE to the first (leftmost) occurrence from the keys with weight equal to WSKV or (if not found) to the first key with weight WSKV+1
> MCO_GT | greater than (>) | Points the CCE to the first key with weight WSKV+1

> To illustrate these rules, consider the first example dataset above and a search value of `2`. The following table shows how the cursor is positioned and what would be the result of the cursor navigation operations prev (previous) and next:

> Search operation | Search result | Description of result
> --- | --- | ---
> MCO_LT | 1 = CCE 2 2 3 4 4 5 | CCE points to key value 1; prev will return `MCO_S_CURSOR_END`; next will return `MCO_S_OK` and will move CCE to key value 2
> MCO_LE | 1 2 2 = CCE 3 4 4 5 | CCE points to rightmost key value 2; prev will return `MCO_S_OK` and will move CCE to key value 2(the leftmost) next will return `MCO_S_OK` and will move CCE to key value 3
> MCO_EQ | 1 2 = CCE 2 3 4 4 5 | CCE points to leftmost key value 2; prev will return `MCO_S_OK` and will move CCE to key value 1 next will return `MCO_S_OK` and will move CCE to key value 2 (the rightmost)
> MCO_GE | 1 2 = CCE 2 3 4 4 5 | CCE points to leftmost key value 2; prev will return `MCO_S_OK` and will move CCE to key value 1 next will return `MCO_S_OK` and will move CCE to key value 2 (the rightmost)
> MCO_GT | 1 2 2 3 = CCE 4 4 5 | CCE points to key value 3; prev will return `MCO_S_OK` and will move CCE to key value 2 (the rightmost) next will return `MCO_S_OK` and will move CCE to key value 4 (the leftmost)

> In the case of the reverse index, again with a search value of `2`:

> Search operation | Search result | Description of result
> --- | --- | ---
> MCO_LT | 5 4 4 3 = CCE 2 2 1 | CCE points to key value 3; prev will return `MCO_S_OK` and will move CCE to key value 4(the rightmost) next will return `MCO_S_OK` and will move CCE to key value 2(leftmost)
> MCO_LE | 5 4 4 3 2 2= CCE 1 | CCE points to key value 2; prev will return `MCO_S_OK` and will move CCE to key value 2(the leftmost) next will return `MCO_S_OK` and move CCE to the key value 1
> MCO_EQ | 5 4 4 3 2 = CCE 2 1 | CCE points to key value 2; prev will return `MCO_S_OK` and move CCE to the key value 3 next will return `MCO_S_OK` and move CCE to the key value 2(the rightmost)
> MCO_GE | 5 4 4 3 2 = CCE 2 1 | CCE points to key value 2; prev will return `MCO_S_OK` and will move CCE to key value 3 next will return `MCO_S_OK` and move CCE to the key value 2(the rightmost)
> MCO_GT | 5 4 4 3 2 2 1 = CCE | CCE points to key value 1; prev will return `MCO_S_OK` and will move CCE to key value 2 (rightmost) next will return `MCO_S_CURSOR_END`

> ## Optimizing tree indexes

> Normally, the B-Tree implementation doesn't store key values in the index. However, for in-memory databases, sometimes it is beneficial to keep the key value on the index pages. See section “Key-Value-Inclusive and Covering Indexes” in this document.