MySQL: B-Tree Index

 When any CREATE TABLE is executed, InnoDB internally creates a clustered B-tree index  representing the table. 
If no primary key is explicitly given, internally a primary key is added. 

Each node of B-tree is represented by one page (which is by default is of size 16KB). 


Below is an useful set of info, copied from other blog
(guptavikas.wordpress.com/2012/12/17/b-tree-index-in-mysql/):


B-Tree is the default index for most storage engines in MySql. 
The general idea of a B-Tree is that all the values are stored in order, and each leaf page is the same distance from the root.

A B-Tree index speeds up data access because the storage engine doesn’t have to scan the whole table to find the desired data. 
Instead, it starts at the root node. The slots in the root node hold pointers to child nodes, and the storage engine follows these pointers.

It finds the right pointer by looking at the values in the node pages, which define the upper and lower bounds of the values in the child nodes. 

Eventually, the storage engine either determines that the desired value doesn’t exist or successfully reaches a leaf page. Leaf pages are special, because they have pointers to the indexed data instead of pointers to other pages.