Database Systems with SQL - Full Course - Database Systems - Multi-Level Indexes and Other Index Types: Hash Bitmap Logical and Function Index

A multi-level index stores column values and row pointers in a hierarchy, where the bottom level is a sparse sorted single-level index and the top-level fits in one block. The way that it work is that it finds a row with an indexed value by reading the top-level blocks first. Then the database compares these indexed values to the block entries in order, and repeatedly, to locate where the bottom-level block that contains the pointer to the value. If the index is dense then it will have more bottom-level entries than if it were a sparse index, and could have more levels. A fan-out of a multi-level index is the number of index entries per block. For most queries, multi-level indexes are faster than single-level indexes. The multi-level index search can read one index block per level. The top two levels are typically small and are stored in memory. Databases typically use multi-level as opposed to single-level indexes they’re faster on most queries. In the example diagram shown, let’s say we did a search for the row that contains FL (Florida). The database first reads the index's top level, sees that FL is between CA and HI, and follows the CA pointer and reads the bottom-level block. FL is between CA and GA so the database then follows the CA pointer, reads the table block, and locates the row containing FL. A branch is each path from the top-level block to a bottom-level. It is ideal to have your branches to be balanced, meaning all branches are the same length. Multi-level indexes are balanced, and are either a B+tree or a B-trees. B+tree. All indexed values appear in the bottom level, and pointers to table blocks appear only in the bottom level. Values are sometimes repeated because some indexed values also appear in higher levels, however the values don’t change levels. Most multi-level indexes are B+ tree implementations since they simpler than B-trees. B-tree. The value is not repeated if an indexed value appears in a higher level, and a pointer to the corresponding table block appears in the higher level along with the value. So, B-trees have no repeated values and are more compact. However, B-tree are harder to implement since table pointers might change levels due to all the inserts, deletes or updates. Multi-level indexes are the most popular type, but there are also less popular types such as a hash index, bitmap index, logical index, or function index. Lets go over a summary of each one: A hash index is basically a hash table that is used to accelerate database queries. It works by converting input records into an array of buckets. Each bucket has the same number of records as all other buckets in the table. No matter how many different values you have for a particular column, every row maps to one bucket. Hash indexes help provide quick lookups on data stored in tables. They work by creating an index key from the value and then locating it based on the resulting hash. It is useful when there is a lot of input with similar values or duplicates, as it only needs to compare keys instead of looking through all records. A bitmap index uses bitmaps, which is a grid of 1 and 0 bits. Each index rows maps to a unique table row, and each index column maps to a distinct table value. A logical index, also referred to as a physical index, is when you create a primary key, secondary key, foreign key, or unique constraint instead of pointers, and the database server ensures referential integrity by creating a logical index for the constraint. A functional index is when an index is defined on the result of a function applied to one or more columns of a single table. Functional indexes can be used to obtain fast access to data based on the result of function calls. Subscribe to Appficial for more programming videos coming soon. Also, don't forget to click LIKE and comment on the video if it helped you out!