B-tree indexes

- [Instructor] Let's turn our attention to balance tree, or B-tree, indexes. As the name implies, the B-tree index is a tree data structure with a root and nodes. The tree is balanced because the root node is the index value that splits the range of values found in the index column. For example, if an index column has values from one to 100 then the root would be 50 or close to 50 if there isn't actually a 50 in the column. Each side of the tree has a sub-tree. The top node of the sub-tree splits the value of the index column so that values less than the node value are stored to the left branch of the tree and values greater than the value in the node are stored to the right. This pattern continues at each level of the tree until we reach the bottom. In this example the B-tree has 11 nodes storing the value of the index column of a table with 11 rows. B-trees make for efficient look-ups because we can always determine where in a tree a node is located by looking at the node value and branching to the left or to the right until we find the value in the tree. In this example, we are looking for the value 15, so we make three comparisons at the nodes 50, 25, and 13 before finding the node with a value of 15. Once we reach the node we want, we can find the reference to where the corresponding row is stored. For example, the index may store the address of a datablock. To summarize, B-trees are the most commonly used type of index. It's used when there are a large number of distinct values in a column. This is called high cardinality. B-trees also rebalance as needed to keep the depth of the tree about the same for all paths. This prevents a lopsided tree that would be fast to search on one side and slower on the other. Anytime you look up a value in the B-tree index, you can expect it to take a time that is proportional to the log of the number of nodes in the tree.