名詞解釋

clustered index（聚集索引）

對（primary key）主鍵索引的一種表述。InnoDB表存儲是基於primary key列來組織的，這樣做可以加快查詢和排序速度。為了獲得最好的性能，在選擇primary key columns的時候要特別小心。因為修改clustered index（聚集索引）列是一個昂貴的操作，所以選擇作為primary的列通常都是很少或者從不會被更新的列。

primary key（主鍵）

A set of columns（一組列），可以唯一標識表中的每一行。因此，它必須是一個unique index，並且不允許有NULL值。

InnoDB organizes the table storage based on the column values of the primary key.

secondary index（輔助索引或二級索引）

索引的一種類型。一個InnoDB表可以有0個或者多個secondary index。

B-tree

tree數據結構在資料庫索引中被廣泛採用。這種結構總是有序的。可以快速查找，精確匹配（等於）或者範圍匹配（比如，大於、小於、BETWEEN等操作）。大多數的存儲引擎都是使用的這種結構，比如InnoDB和MyISAM。

因為B-tree節點可以有許多孩子，一個B-tree和二叉樹不一樣，二叉樹它限制每個結點只能2個孩子。

聚集索引和輔助索引

每個InnoDB表都有一個特別的索引叫clustered index。通常，clustered index和primary key是一個意思。

為了在查詢、插入以及資料庫的其它操作時獲得最好的性能，你必須理解InnoDB中是怎樣使用clustered index優化大多數查詢的。

• 當你在表中定義了一個PRIMARY KEY的時候，InnoDB會把它作為clustered index。在你創建每一張表的時候最好定義一個primary key，如果實在沒有一個或者一組邏輯唯一併且非空的列，你就添加一個新的auto-increment（自增長）的列，讓它的值自動填充。
• 如果你沒有在你的表中定義PRIMARY KEY，那麼MySQL將查找第一個所有值非空的唯一索引列作為clustered index。
• 如果表中沒有PRIMARY KEY，而且也沒有合適的UNIQUE index，那麼InnoDB內部將生產一個名字叫GEN_CLUST_INDEX的隱藏clustered index，其值為行ID

Clustered Index是如何加速查詢的

通過clustered index來訪問一行是非常快的，因為索引檢索直接指向數據所在的頁。如果一個表很大，clustered index架構通常會節省I/O操作。

Secondary Indexes是如何關聯到Clustered Index的

除了clustered index之外的其它索引都叫Secondary Indexes。在secondary index中的每一條記錄包含那一行的primary key列。InnoDB用這個primary key的值來檢索聚集索引中的行。

如果primary key很長，那麼secondary indexes將會占用更多的空間，因此用一個簡短的primary key是有好處的。

一個InnoDB索引的物理結構

InnoDB indexes are B-tree data structures. Index records are stored in the leaf pages of their B-tree data structure. The default size of an index page is 16KB.

當一條新記錄被插入到InnoDB clustered index中時，InnoDB預留page（頁）的1/16的空間以備將來插入或者更新索引記錄。如果索引記錄是順序插入的（升序或者降序），那麼填滿這一頁就是剩下的那15/16的空間；如果記錄是按照隨機順序插入的，那麼填滿這一條就是1/2到15/16頁。配置項innodb_fill_factor定義每個B-tree page 百分之多少的空間用於存儲有序的索引記錄，剩下的空間是為以後索引增長而預留的。

你可以通過innodb_page_size設置InnoDB表空間的page size。支持64KB, 32KB, 16KB (default), 8KB, and 4KB.

小結

1、如果表中沒有定義primary key，則查找第一個不為空的唯一索引列作為聚集索引，若找不到，則生成一個隱藏的聚集索引

2、插入新記錄的時候，預留一頁的1/16的空間用於以後的插入或更新

參考 https://dev.mysql.com/doc/refman/5.7/en/innodb-indexes.html