Database Index

What Is an Index?

An index is a data structure that increases the speed of operations on a table.
An index can be created by using one column or multiple columns in a table.
It provides the basis not only for fast search operations but also for efficient ordering related to record access.
An index is a data structure that improves search speed in a database table by using additional write operations and storage space.
If we want to find specific content in a book, searching every page takes a long time. For that reason, authors add an index at the front or back of a book, and a database index is like a book index.
In databases as well, searching all data in a table takes a long time, so a data structure containing data and the location of the data is created to support fast lookups.
If you query a column without an index, a Full Scan that searches the entire table is performed. Full Scan compares and searches the whole table, so it is slow.

FTS(Full Table Scan)
- A method that searches a table from beginning to end.
Index Scan
- A method that searches an index and accesses the table for the corresponding data.

Hash table
- Implements an index based on a hash generated from column values.
- Search is very fast because the time complexity is O(1).
- Sequential search for continuous data, such as inequalities (<, >), is not possible.
B+Tree
- A data structure that improves a B-Tree, where each node has two or more child nodes.
- It makes sequential search easier by connecting the leaf nodes of a BTree with a LinkedList.
- Although it has worse time complexity, O(log2n), than a hash table, it is used more commonly than hash tables.