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-ow...@postgresql.org
[mailto:pgsql-general-ow...@postgresql.org] On Behalf Of Mike Christensen
Sent: Tuesday, June 05, 2012 3:25 PM
To: pgsql-general@postgresql.org
Subject: [GENERAL] 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@postgresql.org) To make
changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
