"B V, Phanisekhar" <[EMAIL PROTECTED]> wrote:
> How does the index table looks?
>
> Assume the main table to be:
> CREATE TABLE table1 (a INTEGER, b INTEGER)
> Assume there is an index on column a:
> CREATE INDEX index1 ON table1 (a);
>
> Now let's suppose the entries in table1 be:
> 10, 91
> 9, 56
> 89, 78
> 34, 12
> 99, 26
> 19, 77
> 44, 62
> 59, 55
Each table entry also has a hidden ROWID. Let's assume that the
rowids are sequential. Then your data is really this:
1, 10, 91
2, 9, 56
3, 89, 78
4, 34, 12
5, 99, 26
6, 19, 77
7, 44, 62
8, 59, 55
Here the rowids are sequential. That do not have to be. But they
do have to be unique and in increasing order. Because the rowids
are ordered, we can do a binary search to quickly find an entry
with a particular rowid.
>
> Corresponding to this table1 how will index table be?
>
The index on table1(a) consists of all table1.a values followed
by their corresponding rowid, in increasing order:
9, 2
10, 1
19, 6
34, 4
44, 7
59, 8
89, 3
99, 5
> If each data value was unique, then one index lookup would find the
> matching record. Can you explain how this is? Doesn't it will do binary
> search on index table?
>
When you do:
SELECT b FROM table1 WHERE a=34;
SQLite first does a binary search on the index to find the entry
where a==34. From this entry it discovers the rowid. rowid=4.
Then it does a binary search on the table using rowid=4 to find
the corresponding entry in the table. From that entry it sees
that b=12.
So in this case, SQLite has to do two separate binary searches,
one on the index and another on the table.
If, however, you declare your index like this:
CREATE INDEX index1 ON table1(a, b);
Then the index will look like this:
9, 56, 2
10, 91, 1
19, 77, 6
34, 12, 4
44, 62, 7
59, 55, 8
89, 78, 3
99, 26, 5
With this two-column index, if you repeat the same query
SELECT b FROM table1 WHERE a=34
Then SQLite begins as it did before by doing a binary search
on the index to find the row of the index where a==34. But
having found that index row, it can read out the value of b=12
directly, without having to do a second binary search on the
table. The original table is never consulted and the query
runs twice as fast.
--
D. Richard Hipp <[EMAIL PROTECTED]>
-----------------------------------------------------------------------------
To unsubscribe, send email to [EMAIL PROTECTED]
-----------------------------------------------------------------------------
