Index
Index is a separate database object which stores keywords(for searching) and position of rows. Index makes searching easy, which is similar to that of a book.
Although index is a separate database, it depends on the original table. Therefore, in most cases, deleting table also removes index database.
Binary Tree
When searching, looking at all rows is inefficient(full table scan). Therefore, if a set is sorted, it is even better to use binary search.
Binary search decreases the size of searching area into half for each step. First, compare the center value and the target. If the center value is bigger than target, do the same step in the set which only consists of values smaller than center one. If the center value is smaller than target, the other side will be a next searching area.
However, it is difficult to always sort the index. Binary tree solves the problem. Index is usually stored in binary tree structure.
In binary tree, storing and searching value starts at the root node. Basic rule is very simple. Go left side if the value is smaller than the node. Go right in the other case.
For more information, see here.
It is impossible to store same value in binary tree used in index database.
All images, except those with separate source indications, are excerpted from lecture materials.
댓글남기기