索引和算法
索引概述
- B+索引
- 全文索引
- 哈希索引: mysql支持的hash索引是自適應(yīng)的,不能認(rèn)為干預(yù)是否在一張表中生成
數(shù)據(jù)結(jié)構(gòu)和算法
二分查找法
將記錄按有序排列,在查找過程中采用跳躍式的方式查找,即先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象
其中找到頁后,在查找具體行記錄時(shí),在pagedirectory中使用二分查找
二叉查找樹和平衡二叉樹
二叉查找樹
二叉查找樹中,左子樹的鍵值總小于根的鍵值,右子樹的鍵值總大于根的鍵值
平衡二叉樹
首先符合二叉查找樹的定義,其次滿足任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差為1
B+樹
為磁盤或其他直接存取輔助設(shè)備設(shè)計(jì)的一種平衡查找樹,在B+樹種,所有記錄節(jié)點(diǎn)都是按照鍵值的大小放在同一層的葉子節(jié)點(diǎn),有哥哥葉子節(jié)點(diǎn)進(jìn)行連接
聚集索引
按照每張表主鍵構(gòu)造一顆B+樹,同時(shí)葉子節(jié)點(diǎn)存放的即為整張表的行記錄數(shù)據(jù),每張表只能擁有一個(gè)聚集索引,聚集索引的存儲(chǔ)并不是物理連續(xù)的,而是邏輯連續(xù)的,一是每個(gè)頁通過雙向鏈表連接,二是每個(gè)頁中的記錄也通過雙向鏈表連接
輔助索引
即非聚集索引,葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù),葉子節(jié)點(diǎn)除了包含鍵值外,還包含一個(gè)書簽,告訴innodb在哪里找到與索引相對(duì)應(yīng)的行的數(shù)據(jù)
先查找輔助索引,在根據(jù)輔助索引的主鍵id,查找聚集索引
B+樹索引的修改
- Fast Index Creation
對(duì)數(shù)據(jù)表增加S鎖,不影響讀影響寫入 - Online scheme Change
創(chuàng)建臨時(shí)表,將原有數(shù)據(jù)導(dǎo)入,然后同步這段時(shí)間寫入的數(shù)據(jù),最后rename - Online DDl
B+樹索引的使用
聯(lián)合索引
對(duì)表上多個(gè)列進(jìn)行索引,并且按照索引的順序在B+樹上進(jìn)行排序,并且在orderby時(shí)如果按照索引的順序排序,可以避免filesort覆蓋索引
從輔助索引中就可以得到查詢的記錄,不需要查詢聚集索引中的記錄Multi-Range Read優(yōu)化
- MRR是數(shù)據(jù)訪問變得較為順序,在查詢輔助索引時(shí),結(jié)果按照主鍵進(jìn)行排序,在順序查找聚集索引
- 減少緩沖池中頁被替換的次數(shù)
- 批量處理對(duì)鍵值的查詢操作
