How is a B-tree index structured? How does it speed up search?

A B-tree (a balanced tree with multiple keys in a node) is a data structure used in database indexes for efficient search, insertion, and deletion. Unlike a binary tree, each B-tree node contains multiple keys and child pointers, which reduces the tree's height and the number of I/O operations when working with disk.

Main features of B-tree:

• Each node contains from t-1 to 2t-1 keys (where t is the minimum degree).
• All leaves are at the same level, ensuring balance.
• The height of the tree is minimal, speeding up search.

Search acceleration is achieved by:

• Minimizing disk accesses: one read retrieves an entire node with multiple keys.
• Logarithmic search complexity based on the height of the tree.

Example: during a key search, the algorithm compares it with the keys in the node and moves to the corresponding child node until it finds the key or confirms its absence.