What is the principal of index????
Why it is faster when search and sort???
Printable View
What is the principal of index????
Why it is faster when search and sort???
An index is created from one or more columns and is stored outside the table.
Because it only contains data relevant to the search or sort operation, it can be traversed more quickly than the table itself, and is useful for implementing custom search comparison or sort orders since the result of the functions used can be cached in the index.
Indexes are also useful for separating read and write loadings, as indexes can be stored on a different machine to the live database itself.
thank
I want to ask more question
how index use pointer???
And is this statment right?
sort is faster because no swapping is involved
The most important thing about an index is that the keys are sorted.
A record is found in this sorted list using a binary search.
This is a simple and old IT concept where the "middle" key is looked at - if the key to find is less then that then the "bottom" half of the index is looked at next. Otherwise the top half is looked at next. The "middle" key in this part is now looked at - and the operation repeated.
If you have 256 keys and you want to find a value then it takes...
Look 1 - at pos 128
Look 2 - at pos 64 (for instance)
Look 3 - at pos 32 (for instance)
Look 4 - at pos 16 (for instance)
Look 5 - at pos 8 (for instance)
Look 6 - at pos 4 (for instance)
Look 7 - at pos 2 (for instance)
Look 8 - record is found (either pos 1 or 3 - right?)
Note that 2^8 power = 256 - you can find a key with just 8 searches in a list of 256 keys
And that grows fast - 2^16 = 65536 - you can find a key with just 16 searches in a list of 65536 keys.
This is amazingly faster then looking at all 65536 keys - right?
And you get this by simply putting them in sorted order in the index.
This is basically the whole point of an index - fast searching to resolved records.
Now the whole idea of a pointer is that the "data" is not inserted into the database in order.
You don't put record A, B, C, D and E into the table in that order. Of course there are lots more fields going into each of these rows then just the A, B and so on...
So let's say you put D, E, A, C and then B into the table.
These become "internal record numbers" 1, 2, 3, 4 and 5 - right? That's the order they are put in.
But the index must be sorted by the "keys" - so the index appears as a list like this:
A - pointing to 3
B - pointing to 5
C - pointing to 4
D - pointing to 1
E - pointing to 2
If we want to find C we go to the index - it's in the middle position so of course we find it first - and the pointer says it's in data record # 4.
Indexes are expensive for the database engine to maintain - as putting keys into sorted position means either moving or splitting existing keys. And that's exactly what is done - as the "index leaves" fill with keys they might split into two other leaves - but this is getting beyond the scope of your original questions.
Your question though...
is not a major reason for indexes.Quote:
sort is faster because no swapping is involved
They are for searching - joining - and relating rows.
You might have an INDEX on NAME for instance - in an employee table - and those times you ORDER BY NAME will be fast, since no sorting is required to achieve this order. The rows are simply read "according" to the index - from start to finish - they come out sorted by default. But again you should not be adding indexes because of sort orders - more often they are added because of relationship and search speeds.
Thank you for your professional reply.
Is it means that index is only benefit to search but not sorting?
May I ask one more term about index?
What is B-tree???
The Internet say that all leaves are sorted at the same distance from the root.
But I still feel puzzled.
I did not say that - I did indicate a situation (the ORDER BY NAME sort at the end of my post) where SORTING can be helped by an INDEX. But that is only because the "keys" and thus the "pointers" are already pre-sorted. It is a rare situation in a large scale DB system where you offer indexes for all your ORDER BY conditions in all your queries.Quote:
Originally Posted by s021126
This is a much more complex concept - probably one better served by you doing research - there are many good books on index concepts.Quote:
May I ask one more term about index?
What is B-tree???
But in a nutshell - a b-tree "summarizes" the "keys" in a hierarchy of levels. Only so many keys can fit in a "disk page" - and they are not usually evenly distributed. And I/O is the most expensive operation for a database engine.
So it makes sense to have a upper level of leaves that indicates what leaves below have what "key ranges".
Basically single keys are removed from the leaves below and brought up to a upper leaf. When searching this upper leaf is first looked at to tell the engine what leaves below most likely hold the key we are looking for.
This link explains the concept:
http://en.wikipedia.org/wiki/B-tree