What indices do you know? How does a B-tree index work?

There are different types of indexes in databases, the main ones are:

• B-tree (balanced tree): the most common type of index for fast search, insertion, and deletion. Data is organized as a tree, where each node contains keys and references to child nodes. Search occurs in logarithmic time.

• Hash indexes: use hash functions for quick access by exact key value, but are not suitable for range queries.

• Bitmap indexes: effective for columns with a small number of unique values.

• Full-text indexes: for fast text search.

How B-tree index works:

• Data is stored in sorted order in leaf nodes.
• Internal nodes contain keys for navigation.
• Search starts from the root, compares the key, selects the appropriate child node, and repeats until reaching a leaf.
• Insertion and deletion maintain the balance of the tree to keep the depth minimal, ensuring quick access.

Example: if searching for a record with key 50, the B-tree quickly determines the path to the leaf where this key may be located, without scanning the entire table.