In a database, an index is a way to speed up the retrieval of data. Indexes work by ordering the values in a column or set of columns from a table on disk and then linking the rest of the record back to indexed value. Normally, the database management system must search through every record one at a time to find records that match specific conditions. With an index the system can quickly retrieve data that is conditioned on an indexed column or columns by eliminating other rows. Any column could technically be made into an index and a table could have any number of indexes; however, for each table in a query, generally only one index can be used. Some good columns to index on include columns used in JOINs and columns that are important to the functionality of the database (such as first and last name for a bank balance database).
Because we are primarily using MySQL in class, I did the majority of my investigation into the internal aspects of indexing based on this database system. MySQL supports several different storage engines (underlying software responsible for the management and changing of data being stored in the database) which use different types of indexing (or multiple types of indexing depending on the specification of the user). The default engine InnoDB mainly uses B-Tree indexes for internal index storage. This works in a similar way to the binary search trees we talked about in class, but multiple values are allowed at each level (instead of two). Another way a column can be indexed in MySQL is through a Hash table. This requires a different storage engine than InnoDB. A hash table index gives an address to each value in the column and then uses that value to directly find the data associated. While the hash table index is faster, the B-Tree index allows for ranges and comparison (the hash table can only search by = or <>). There are also several other index structures in MySQL.
Something to note about indexes is that they cause a tradeoff. While they make queries quicker, they require more space in the disk (to support the index structure) which can be problematic for large datasets. They also have a time tradeoff, any insert statement must also change the structure of the index associated, meaning inserts take longer.
While there are a lot of complicated pieces of SQL code that can be used in indexing, I will focus on explaining simple index creation using the default storage engine InnoDB. InnoDB is generally considered the best to use because it is transactional, meaning either the entire statement is executed or none of it is (reverses changes in the case of errors). The general statement for creating an index is…
CREATE INDEX name
ON table(column1);
Note: indexes can use multiple columns.
This will create an index that is used automatically to speed up queries involving the columns used in the index. Such as…
SELECT *
FROM table
WHERE column1 BETWEEN value AND value;
You can also create unique indexes (CREATE UNIQUE INDEX) which double as a constraint meaning duplicate values will not be allowed in that column. While indexing can be very (very) complicated, I hope I have given you a quick run-down on the basics of how they vary, work, and can be used within our MySQL projects. Here are some sources to use to learn more.
Simple Index Tutorial w3schools:
https://www.w3schools.com/sql/sql_create_index.asp
A little outdated, but a great overview of indexing in MySQL:
https://www.oreilly.com/library/view/high-performance-mysql/0596003064/ch04.html
What columns make good indexes?
https://stackoverflow.com/questions/107132/what-columns-generally-make-good-indexes
MySQL Index Documentation:
https://dev.mysql.com/doc/refman/8.0/en/create-index.html
Another good source – related to a topic I could not figure out B-Trees vs B+Trees:
https://www.vertabelo.com/blog/all-about-indexes-part-2-mysql-index-structure-and-performance/
Another difficult topic-B-Trees vs Binary Trees:
https://techdifferences.com/difference-between-b-tree-and-binary-tree.html
B-trees explained:
https://www.cs.cornell.edu/courses/cs3110/2012sp/recitations/rec25-B-trees/rec25.html