From Suhrid.net WikiJump to navigationJump to search
These are notes that I took about SQL Indexing from http://use-the-index-luke.com
- An index makes a SQL query fast.
- An index is a distinct structure in the DB that requires its own space.
- A DB index is similar to index of a book - key concept is all entries are arranged in a well-defined order. Finding data in an ordered set is fast and easy because the sort order determines each entries position.
- A DB index however undergoes constant change. Whenever INSERT, UPDATE, DELETE's are executed, the index must also be updated without moving around large amounts of data.
- The DB combines two data structures for providing indexing - doubly linked lists and search trees.
- Doubly linked list enables DB to read indexes forwards and backwards. Index leaf nodes store the indexes in a DB block or page. The blocks are logically stored in the doubly linked list.
- The Index Leaf nodes however are stored in an arbitrary order on the disk - not according to logical order. Therefore the DB needs a second data structure to find the index leaf nodes quickly.
- This is the Balanced Tree : B-Tree. The branch nodes store the max value of the index leaf node. The root node in turn points to the branch node.
- Traversing a B-Tree is efficient. Tree depth grows logarithmically compared to the number of indexes.
- However, an index leaf node can contain multiple entries for the same index. Perhaps even across leaf nodes. So after tree traversal, the DB has to scan the index leaf nodes. So query can be slow even if there is an index on the column.