Thread: Universal B-tree

Dear developers,<br /><br />I'm PhD candidate in Brazil and a newbie on postgresql developement, sorry for any silly
questions.I implemented a new algorithm for range search using universal b-tree but I don't have a clue how to
integrateit into postgresql.<br /><br />Where I can find the resources about it?<br /><br /> I don't need to change
B-treeestructure. I just need integrate my encode function that transforms multiple keys into one key by
bit-interleavingand to acess elements given several intervals (range search).<br /><br />I've heard about a framework
ATOMon the article "Native Multidimensional Indexing in Relational Databases" written by David Hoksza, Tomas Skopal
whichsays that ATOM abstracts the way that postgres records information... does any one know where I can get it?<br
/><br/>Best regards,<br /><br />Daniel Oliveira<br /> 

On Mon, Aug 9, 2010 at 5:31 PM, Daniel Oliveira
<danielmarquesoliveira@gmail.com> wrote:
> I don't need to change B-tree estructure. I just need integrate my encode
> function that transforms multiple keys into one key by bit-interleaving and
> to acess elements given several intervals (range search).

You could build a "expression" index on the function which will build
a regular btree. Then any range clause on a similar expression in the
query would be able to use the index. Postgres is capable of detecting
multiple range clauses that can use one or more indexes and combine
the results.  It might not be perfect for your use case, being a
general purpose tool.

I'm not sure how feasible it would be to implement a special purpose
case that matches your needs. Perhaps a special index type and index
access method similar to gist "tsquery" data type. But that's a lot
more work and a lot more C coding.

-- 
greg

For research purpose, I think that expression index is a good idea. I just want to do a proof of concept.<br /><br
/>Theother issue is that my algorithm break a z-order interval into several intervals that represents the query box.
Howshould I create it without creating any overhead?<br /><br />Best regards,<br /><br />daniel<br /><br /><div
class="gmail_quote">2010/8/9Greg Stark <span dir="ltr"><<a
href="mailto:gsstark@mit.edu">gsstark@mit.edu</a>></span><br/><blockquote class="gmail_quote" style="margin: 0pt 0pt
0pt0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">On Mon, Aug 9, 2010 at 5:31
PM,Daniel Oliveira<br /> <<a href="mailto:danielmarquesoliveira@gmail.com">danielmarquesoliveira@gmail.com</a>>
wrote:<br/> > I don't need to change B-tree estructure. I just need integrate my encode<br /> > function that
transformsmultiple keys into one key by bit-interleaving and<br /> > to acess elements given several intervals
(rangesearch).<br /><br /></div>You could build a "expression" index on the function which will build<br /> a regular
btree.Then any range clause on a similar expression in the<br /> query would be able to use the index. Postgres is
capableof detecting<br /> multiple range clauses that can use one or more indexes and combine<br /> the results.  It
mightnot be perfect for your use case, being a<br /> general purpose tool.<br /><br /> I'm not sure how feasible it
wouldbe to implement a special purpose<br /> case that matches your needs. Perhaps a special index type and index<br />
accessmethod similar to gist "tsquery" data type. But that's a lot<br /> more work and a lot more C coding.<br /><br />
--<br/><font color="#888888">greg<br /></font></blockquote></div><br /> 

Daniel Oliveira wrote:
> There is a way to acess a index inside a c function without using a 
> sql statement ?
Yes, if you know the oid of the index you want to scan, you can use 
functions from backend/access/index/indexam.c.

regards,
Yeb Havinga