Mysql索引底層數據結構

Mysql索引底層數據結構課題大綱1.索引優(yōu)化面試題分析2.索引數據結構3.MyISAM和InnoDB索引實現索引優(yōu)化面試題分析CREATETABLE`employees`(`id`int(11)NOTNULLAUTO_INCREMENT,`name`varchar(24)NOTNULLDEFAULT''COMMENT'姓名',`age`int(11)NOTNULLDEFAULT'0'COMMENT'年齡',`position`varchar(20)NOTNULLDEFAULT''COMMENT'職位',`hire_time`timestampNOTNULLDEFAULTCURRENT_TIMESTAMPCOMMENT'入職時間',PRIMARYKEY(`id`),KEY`idx_name_age_position`(`name`,`age`,`position`)USINGBTREE)ENGINE=InnoDBAUTO_INCREMENT=4DEFAULTCHARSET=utf8COMMENT='員工記錄表';INSERTINTOemployees(name,age,position,hire_time)VALUES('LiLei',22,'manager',NOW());INSERTINTOemployees(name,age,position,hire_time)VALUES('HanMeimei',23,'dev',NOW());INSERTINTOemployees(name,age,position,hire_time)VALUES('Lucy',23,'dev',NOW());索引優(yōu)化面試題分析分析以下幾條sql的索引使用情況SELECT*FROMemployeesWHEREname='LiLei';SELECT*FROMemployeesWHEREname='LiLei'ANDage=22ANDposition='manager';SELECT*FROMemployeesWHEREage=22ANDposition='manager';SELECT*FROMemployeesWHEREname='LiLei'ANDage>22ANDposition='manager';SELECT*FROMemployeesWHEREname!='LiLei';Mysql索引定義MySQL官方對索引的定義為：

索引（Index）是幫助MySQL高效獲取數據的數據結構

索引的本質：

索引是數據結構，而且是實現了高級查找算法的數據結構索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤I/O操作索引結構索引結構二叉樹紅黑樹HASHBTREE數據結構教學網站：/~galles/visualization/Algorithms.html磁盤存取原理

尋道時間(速度慢，費時)

旋轉時間(速度較快)

預讀：長度為頁的整倍數（主存和磁盤以頁為單位交換數據，一頁4K）Hash索引如果是等值查詢，哈希索引明顯有絕對優(yōu)勢，前提：鍵值唯一哈希索引沒辦法完成范圍查詢檢索哈希索引也沒辦法利用索引完成排序，以及l(fā)ike‘xxx%’這樣的部分模糊查詢哈希索引也不支持多列聯(lián)合索引的在有大量重復鍵值情況下，哈希索引的效率也最左前綴原則是極低的，因為存在哈希碰撞問題B-TreeB-Tree度(Degree)-節(jié)點的數據存儲個數葉節(jié)點具有相同的深度葉節(jié)點的指針為空節(jié)點中的數據key從左到右遞增排列B+TreeB+Tree(B-Tree變種)非葉子節(jié)點不存儲data，只存儲key，可以增大度葉子節(jié)點不存儲指針順序訪問指針，提高區(qū)間訪問的性能B+TreeB+Tree索引的性能分析一般使用磁盤I/O次數評價索引結構的優(yōu)劣預讀：磁盤一般會順序向后讀取一定長度的數據(頁的整數倍)放入內存局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用B+Tree節(jié)點的大小設為等于一個頁，每次新建節(jié)點直接申請一個頁的空間，這樣就保證一個節(jié)點物理上也存儲在一個頁里，就實現了一個節(jié)點的載入只需一次I/OB+Tree的度d一般會超過100，因此h非常小(一般為3到5之間)MyISAM索引實現MyISAM索引實現(非聚集)MyISAM索引文件和數據文件是分離的InnoDb索引實現InnoDB索引實現(聚集)數據文件本身就是索引文件表數據文件本身就是按B+Tree組織的一個索引結構文件聚集索引-葉節(jié)點包含了完整的數據記錄為什么InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？