USAGE 1 : Support for fast Lookup
An index is any data structure that improves the performance of lookup. There are many different
data structures
used for this purpose. There are complex design trade-offs involving lookup performance, index size, and index-update performance. Many index designs exhibit logarithmic (O(log(N)) lookup performance and in some applications it is possible to achieve flat (O(1)) performance.
USAGE 2 : Policing the database constraints (I assumed it as a DB table guideline)
Indexes are used to police
database constraints
, such as UNIQUE, EXCLUSION,
PRIMARY KEY
and
FOREIGN KEY
.
-index가 없으면 full scan 함
-index가 있다면 쉽게 B-tree 구조로 되어 스캔(시간단축된다)
-like 를 쓸 때에는 index가 있더라도 full scan 될 수 있음
Indexes are useful for many applications but come with some limitations. Consider the following
SQL
statement: SELECT first_name FROM people WHERE last_name = 'Smith';. To process this statement without an index the database software must look at the last_name column on every row in the table (this is known as a
full table scan
). With an index the database simply follows the
B-tree
data structure until the Smith entry has been found; this is much less computationally expensive than a full table scan.
Consider this SQL statement: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. This query would yield an email address for every customer whose email address ends with “@wikipedia.org”, but even if the email_address column has been indexed the database must perform a full index scan. This is because the index is built with the assumption that words go from left to right. With a
wildcard
at the beginning of the search-term, the database software is unable to use the underlying B-tree data structure (in other words, the WHERE-clause is not
sargable
). This problem can be solved through the addition of another index created on reverse(email_address) and a SQL query like this: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. This puts the wild-card at the right-most part of the query (now gro.aidepikiw@%), which the index on reverse(email_address) can satisfy.
When the wildcard characters are used on both sides of the search word as %wikipedia.org%, the index available on this field is not used. Rather only a sequential search is performed, which takes O(N) time.
Main article: Bitmap index
A bitmap index is a special kind of indexing that stores the bulk of its data as bit arrays (bitmaps) and answers most queries by performing bitwise logical operations on these bitmaps. The most commonly used indexes, such as B+ trees , are most efficient if the values they index do not repeat or repeat a small number of times. In contrast, the bitmap index is designed for cases where the values of a variable repeat very frequently. For example, the sex field in a customer database usually contains at most three distinct values: male, female or unknown (not recorded). For such variables, the bitmap index can have a significant performance advantage over the commonly used trees.
quotes from wiki