Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
22 Cards in this Set
- Front
- Back
|
DB admins consider indexes to be... |
the single most critical tool for improving database performance |
|
|
an index is a... |
persistent data structure that contains an organized copy of some of the data from one or more existing database tables. |
|
|
A database index provides... |
an organizational framework that the DBMS can use to quickly locate the information it needs. |
|
|
an index can vastly improve... |
the speed which SQL queries can be answered |
|
|
Sequential search; average and worse case |
average: (n+1) / 2 worst: n |
|
|
Binary search; average and worst case |
average: log_2(n) - 1 worst: log_2(n) |
|
|
without an index... |
the DBMS has to perform a table scan in order to locate the desired row(s) |
|
|
INDEXES are created on... |
one or more columns in a table |
|
|
an INDEX is created on... |
a Primary Key column (SQL command to create Index) |
|
|
The INDEX will contain the... |
PK for each row in the table along with each row's ordinal position (row number) in the table. (can keep PKs in sorted order). |
|
|
When a query involving the PK is run, the DBMS will... |
find the PK within the index. The DBMS will then know the position of the row within the table. |
|
|
When the DBMS knows the position of the row within the table, the DBMS can then... |
quickly/directly locate the row in the table that is associated with the PK involved in the query. |
|
|
Creating an INDEX... |
increases the amount of storage space required by the database |
|
|
This occurs because... |
an index contains a copy of some of the data in a table |
|
|
To estimate the storage space requirements of an index... |
Number of rows in table * Average number of bytes required per row for the indexed column 98000rows * (16bytes/row + 2deptID) = 1764000 bytes |
|
|
Index => difference between table scans and immediate location of tuples: |
Orders of magnitude performance difference |
|
|
Underlying basic data structures: |
a. Balanced trees(B trees, B+ trees): i. used to locate tuples where : Attribute = value; Attribute < value; Attribute > value or in a range of values ii. Logarithmic time to search, insert, or delete. b. Hash tables i. only be used for attribute = value ii. GOOD hash tables - constant time |
|
|
Performance gains are well worth... |
the extra space |
|
|
An index on the student ID will allow... |
the query execution engine to go pretty much straight to that tuple, whereas without an index the entire student (t)able would have to be scanned. |
|
|
many DBMS's build indexes... |
automatically on PRIMARY KEY (and sometimes UNIQUE) attributes. |
|
|
even more choices of how to use indexes gets into the entire area of what is known as... |
query planning and query optimization |
|
|
Indexes is actually one of the most exciting and interesting areas of... |
the implementation of database systems and is what allows us to have a declarative query language that's implemented efficiently |
