Re: b-tree index search algorithms

Am 20.07.12 01:40, schrieb Tom Lane:
> RelationGetDescr(rel)->attrs[n]->attbyval

Thanks!
Now does 'Relation' refer to the whole table or only the columns that 
are supposed to be scanned? So will RelationGetDescr(rel)->attrs[0] give 
me the description of the first column relevant to the current b-tree 
scan or simply to the first column in the table?
Naively I tried RelationGetDescr(rel)->attrs[scankey->sk_attno] but it 
results in a segmentation fault.

A first version of my algorithm is running now (very simple test case) 
but I had to implement a workaround for the following behavior: The 
(binary) search is supposed to always find the first matching offset on 
a page, but I do not understand how this is guaranteed, since the 
semantics of a binary search do not guarantee this. The type being 
searched where it throws me off specifically is a 'chunk_id', page 
contents are:
1: 12000
2: 12001
3: 12002
4: 12003
5: 12004
6: 12004
7: 12005
8: 12005
9: 12006
10: 12006
11: 16393
12: 16393
13: 16394
14: 16394
15: 16395
16: 16395

Binary search finds 11 in 4 steps, interpolation search finds 12 in 3 
steps. Now if there was an additional value like "17: 16396", binary 
search should also find 12 first, right?

Regards,
Samuel Vogel