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.