|
1 | | -$Header: /cvsroot/pgsql/src/backend/access/nbtree/README,v 1.3 2000/07/21 22:14:09 tgl Exp $ |
| 1 | +$Header: /cvsroot/pgsql/src/backend/access/nbtree/README,v 1.4 2000/07/25 05:26:40 tgl Exp $ |
2 | 2 |
|
3 | 3 | This directory contains a correct implementation of Lehman and Yao's |
4 | 4 | high-concurrency B-tree management algorithm (P. Lehman and S. Yao, |
@@ -119,6 +119,17 @@ In addition, the following things are handy to know: |
119 | 119 | exists only to support VACUUM and allow it to delete items while |
120 | 120 | it's scanning the index. |
121 | 121 |
|
| 122 | ++ "ScanKey" data structures are used in two fundamentally different ways |
| 123 | + in this code. Searches for the initial position for a scan, as well as |
| 124 | + insertions, use scankeys in which the comparison function is a 3-way |
| 125 | + comparator (<0, =0, >0 result). These scankeys are built within the |
| 126 | + btree code (eg, by _bt_mkscankey()) and used by _bt_compare(). Once we |
| 127 | + are positioned, sequential examination of tuples in a scan is done by |
| 128 | + _bt_checkkeys() using scankeys in which the comparison functions return |
| 129 | + booleans --- for example, int4lt might be used. These scankeys are the |
| 130 | + ones originally passed in from outside the btree code. Same |
| 131 | + representation, but different comparison functions! |
| 132 | + |
122 | 133 | Notes about data representation: |
123 | 134 |
|
124 | 135 | + The right-sibling link required by L&Y is kept in the page "opaque |
|