In this video, learn about balanced 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.
Author
Released
4/1/2019- How SQL executes queries
- Working with PostgreSQL tools for tuning
- Bitmap and hash indexes
- Using different types of indexes to improve performance
- Challenges with joining tables
- When to use partitioning to improve performance
- Collecting statistics about data in tables
Skill Level Advanced
Duration
Views
Related Courses
-
Advanced SQL for Data Scientists
with Dan Sullivan1h 24m Advanced -
Introduction to Spark SQL and DataFrames
with Dan Sullivan1h 53m Intermediate
-
Introduction
-
1. How SQL Executes a Query
-
Scanning tables and indexes3m 12s
-
Joining tables2m 24s
-
Partitioning data2m 23s
-
2. PostgreSQL Tools for Tuning
-
Installing PostgreSQL2m 41s
-
Overview of pgAdmin3m 21s
-
Explain and analyze3m 37s
-
Indexes3m 7s
-
-
3. Types of Indexes
-
Indexing3m 1s
-
B-tree indexes2m 2s
-
B-tree index example plan2m 18s
-
Bitmap indexes1m 46s
-
Bitmap index example plan2m 39s
-
Hash indexes1m 19s
-
Hash index example plan1m 32s
-
PostgreSQL-specific indexes1m 17s
-
-
4. Tuning Joins
-
Nested loops3m 19s
-
Nested loop example plan3m 55s
-
Hash joins1m 25s
-
Hash join example plan1m 57s
-
Merge joins2m 17s
-
Merge join example3m 16s
-
Subqueries vs. joins1m 11s
-
5. Partitioning Data
-
Partition by range2m 6s
-
Partition by list1m 37s
-
Partition by list example4m 55s
-
Partition by hash2m 12s
-
Partition by hash example4m 51s
-
6. Materialized Views
-
Materialized views1m 41s
-
-
7. Other Optimization Techniques
-
Hints to the query optimizer2m 13s
-
Parallel query execution2m 3s
-
Miscellaneous tips1m 47s
-
Conclusion
-
Next steps41s
-
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.
CancelTake notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.
Share this video
Embed this video
Video: B-tree indexes