how B-tree indexing works in mysql
b-tree, database, mysql, search
Solution
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".
Problem
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?