Results 1 to 6 of 6

Thread: Question about index

  1. #1

    Thread Starter
    Lively Member
    Join Date
    Jun 2006
    Posts
    96

    Question about index

    What is the principal of index????
    Why it is faster when search and sort???

  2. #2
    I'm about to be a PowerPoster!
    Join Date
    Jan 2005
    Location
    Everywhere
    Posts
    13,647

    Re: Question about index

    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.

  3. #3

    Thread Starter
    Lively Member
    Join Date
    Jun 2006
    Posts
    96

    Re: Question about index

    thank
    I want to ask more question
    how index use pointer???
    And is this statment right?
    sort is faster because no swapping is involved

  4. #4
    MS SQL Powerposter szlamany's Avatar
    Join Date
    Mar 2004
    Location
    Connecticut
    Posts
    18,263

    Re: Question about index

    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...

    sort is faster because no swapping is involved
    is not a major reason for indexes.

    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.
    Last edited by szlamany; Dec 1st, 2007 at 10:32 AM.

    *** Read the sticky in the DB forum about how to get your question answered quickly!! ***

    Please remember to rate posts! Rate any post you find helpful - even in old threads! Use the link to the left - "Rate this Post".

    Some Informative Links:
    [ SQL Rules to Live By ] [ Reserved SQL keywords ] [ When to use INDEX HINTS! ] [ Passing Multi-item Parameters to STORED PROCEDURES ]
    [ Solution to non-domain Windows Authentication ] [ Crazy things we do to shrink log files ] [ SQL 2005 Features ] [ Loading Pictures from DB ]

    MS MVP 2006, 2007, 2008

  5. #5

    Thread Starter
    Lively Member
    Join Date
    Jun 2006
    Posts
    96

    Re: Question about index

    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.
    Last edited by s021126; Dec 2nd, 2007 at 12:05 AM.

  6. #6
    MS SQL Powerposter szlamany's Avatar
    Join Date
    Mar 2004
    Location
    Connecticut
    Posts
    18,263

    Re: Question about index

    Quote Originally Posted by s021126
    Is it means that index is only benefit to search but not sorting?
    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.

    May I ask one more term about index?
    What is B-tree???
    This is a much more complex concept - probably one better served by you doing research - there are many good books on index concepts.

    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

    *** Read the sticky in the DB forum about how to get your question answered quickly!! ***

    Please remember to rate posts! Rate any post you find helpful - even in old threads! Use the link to the left - "Rate this Post".

    Some Informative Links:
    [ SQL Rules to Live By ] [ Reserved SQL keywords ] [ When to use INDEX HINTS! ] [ Passing Multi-item Parameters to STORED PROCEDURES ]
    [ Solution to non-domain Windows Authentication ] [ Crazy things we do to shrink log files ] [ SQL 2005 Features ] [ Loading Pictures from DB ]

    MS MVP 2006, 2007, 2008

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width