how B-tree indexing works in mysql

Question

When I create an index for a table in mysql, I see that the index_type is type BTREE. Now although I understand about btree(s), I do not quiet understand how it stores the index and how the database searches the records based on this.

I mean, btree is excellent for databases to perform read and writes large blocks of data, when we create an index for column type of Primary key, what I understand is, it creates a tree and splitting the values for the root based on the value type of the root.

Now, does it store only the the primary key ID under the trees or the whole data associated with that primary key?

After finding the wanted primary ID, how does the database extract the record?

Answer 1

The database stores the value indexed as a B-Tree key, and the record pointer as a B-Tree value.

Whenever you search for a record holding a certain value of an indexed column, the engine locates the key holding this value in the B-Tree, retrieves the pointer to the record and fetches the record.

What exactly is a "record pointer", depends on the storage engine.

• In MyISAM, the record pointer is an offset to the record in the MYI file.

• In InnoDB, the record pointer is the value of the PRIMARY KEY.

In InnoDB, the table itself is a B-Tree with a PRIMARY KEY as a B-Tree key. This is what called a "clustered index" or "index-organized table". In this case, all other fields are stored as a B-Tree value.

In MyISAM, the records are stored without any special order. This is called "heap storage".

Answer 2

MySQL InnoDB is actually using B+Tree which add more features than B-Tree.

Such as:

Only leaves node has values to allow more keys in the same page node to reduce tree high which will reduce I/O count.

Add a bidirectional pointer in each leaf node to make range search faster

B-Tree

B+Tree