If you want to discover how B+Trees or B-Trees work, I suggest a web search. A database like PostgreSQL is not going to use an ordinary btree for an index, but they use special trees that have page level structures, such as B-Trees, GiST trees, etc. For PostgreSQL the list includes {IIRC} B-tree, Hash, GiST and GIN, though I am not sure it is current. I believe that there is also a GIS extension to PostgreSQL which probably uses Octrees or Quadtrees, but that is purely a guess.
Place this criteria into your favorite search engine, for instance:
"B-Tree" index
You can qualify it with "PostgreSQL" if you like, but I suspect you just want to know how indexes work in general with different index types.
I suspect that what you really want to eventually understand is:
"How does the optimizer make plans to create efficient queries" which is what is indicated in your questions below.
If that is the case, then I suggest performing search queries with keywords such as:
sql cost based optimizer
-----Original Message-----
From: pgsql-general-owner@xxxxxxxxxxxxxx [mailto:pgsql-general-owner@xxxxxxxxxxxxxx] On Behalf Of Mike Christensen
Sent: Tuesday, June 05, 2012 3:25 PM
To: pgsql-general@xxxxxxxxxxxxxx
Subject: I'd like to learn a bit more about how indexes work
Hi -
I'm trying to increase my general knowledge about how indexes work in databases. Though my questions are probably general and implemented in a similar way across major relational DBs, I'm also curious as to how they're implemented in Postgres specifically (mainly because I like PG, and am always interested in knowing if PG does things in some cool and interesting way).
I know the basics of how binary trees work, so I understand a query such as :
select * from Table where Id = 5;
Provided Id has a btree index on it. I'm curious as to how indexes are used with OR and AND clauses.
Something like:
select * from Table where X = 5 or y = 3;
It seems to me both the index of X would be scanned and those rows would be loaded into memory, and then the index of Y would be scanned and loaded. Then, Postgres would have to merge both sets into a set of unique rows. Is this pretty much what's going on? Let's ignore table stats for now.
Then, something like:
select * from Table where X = 5 AND y = 3;
I would imagine the same thing is going on, only Postgres would find rows that appear in both sets. I also imagine Postgres might create a hash table from the larger set, and then iterate through the smaller set looking for rows that were in that hash table.
Lastly, If you had a query such as:
select * from Table where X IN (1,2,3,4,5,6,7);
I would imagine Postgres would parse that query as a bunch of OR clauses. Does this mean the index for X would be scanned 7 times and merged into a set of unique results? Though, obviously if Postgres estimated this would return the majority of the rows in the table, it would probably just ignore the index completely.
Thanks!
Mike
--
Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx) To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
--
Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
