MySQL數(shù)據(jù)庫有如下幾種常見的索引類型:
- BTree索引
- 哈希索引
- 全文索引
索引的本質(zhì)
MySQL官方對索引的定義為:索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)颈渊。提取句子主干杆融,就可以得到索引的本質(zhì):索引是數(shù)據(jù)結(jié)構(gòu)袁串。
最基本的查詢算法當(dāng)然是順序查找(linear search),這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時顯然是糟糕的恼五,好在計算機科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法,例如二分查找(binary search)惨驶、二叉樹查找(binary tree search)等袭艺。
每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上,例如二分查找要求被檢索數(shù)據(jù)有序佑稠,而二叉樹查找只能應(yīng)用于二叉查找樹上秒梅,但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)(例如,理論上不可能同時將兩列都按順序進行組織)舌胶,所以捆蜀,在數(shù)據(jù)之外,數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)幔嫂,這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用(指向)數(shù)據(jù)辆它,這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)履恩,就是索引娩井。
BTree索引
B-Tree和B+Tree
(1)B-Tree
為了描述B-Tree,首先定義一條數(shù)據(jù)記錄為一個二元組[key, data]似袁,key為記錄的鍵值洞辣,對于不同數(shù)據(jù)記錄,key是互不相同的昙衅;data為數(shù)據(jù)記錄除key外的數(shù)據(jù)扬霜。那么B-Tree是滿足下列條件的數(shù)據(jù)結(jié)構(gòu):
- d為大于1的一個正整數(shù),稱為B-Tree的度而涉。
- h為一個正整數(shù)著瓶,稱為B-Tree的高度。
- 每個非葉子節(jié)點由n-1個key和n個指針組成啼县,其中d<=n<=2d材原。
- 每個葉子節(jié)點最少包含一個key和兩個指針,最多包含2d-1個key和2d個指針季眷,葉節(jié)點的指針均為null 余蟹。
- 所有葉節(jié)點具有相同的深度,等于樹高h子刮。
- key和指針互相間隔威酒,節(jié)點兩端是指針窑睁。
- 一個節(jié)點中的key從左到右非遞減排列。
- 所有節(jié)點組成樹結(jié)構(gòu)葵孤。
- 每個指針要么為null担钮,要么指向另外一個節(jié)點。
B-Tree查找:首先從根節(jié)點進行二分查找尤仍,如果找到則返回對應(yīng)節(jié)點的data箫津,否則對相應(yīng)區(qū)間的指針指向的節(jié)點遞歸進行查找,直到找到節(jié)點或找到null指針宰啦,前者查找成功苏遥,后者查找失敗
B-Tree特性:一個度為d的B-Tree,設(shè)其索引N個key绑莺,則其樹高h的上限為logd((N+1)/2),檢索一個key惕耕,其查找節(jié)點個數(shù)的漸進復(fù)雜度為O(logdN)
(2)B+Tree
MySQL就普遍使用B+Tree實現(xiàn)其索引結(jié)構(gòu)纺裁,與B-Tree相比,B+Tree有以下不同點:
- 每個節(jié)點的指針上限為2d而不是2d+1司澎。
-
內(nèi)節(jié)點不存儲data欺缘,只存儲key;葉子節(jié)點不存儲指針挤安。
圖3是一個簡單的B+Tree示意谚殊。
B+Tree示意
一般在數(shù)據(jù)庫系統(tǒng)或文件系統(tǒng)中使用的B+Tree結(jié)構(gòu)都在經(jīng)典B+Tree的基礎(chǔ)上進行了優(yōu)化,增加了順序訪問指針蛤铜,示例如下:
帶有順序訪問指針的B+Tree
做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能嫩絮,例如上圖中如果要查詢key為從18到49的所有數(shù)據(jù)記錄,當(dāng)找到18后围肥,只需順著節(jié)點和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點剿干,極大提到了區(qū)間查詢效率。
為什么使用B-Tree(B+Tree)
在計算機存儲介質(zhì)中穆刻,磁盤本身存取就比主存慢很多置尔,再加上機械運動耗費,磁盤的存取速度往往是主存的幾百分分之一氢伟,因此為了提高效率榜轿,要盡量減少磁盤I/O。為了達到這個目的朵锣,磁盤往往不是嚴(yán)格按需讀取谬盐,而是每次都會預(yù)讀,即使只需要一個字節(jié)诚些,磁盤也會從這個位置開始设褐,順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機科學(xué)中著名的局部性原理。
預(yù)讀的長度一般為頁(page)的整倍數(shù)助析。頁是計算機管理存儲器的邏輯塊犀被,硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊,每個存儲塊稱為一頁(在許多操作系統(tǒng)中外冀,頁得大小通常為4k)寡键,主存和磁盤以頁為單位交換數(shù)據(jù)。
根據(jù)B-Tree的定義雪隧,可知檢索一次最多需要訪問h個節(jié)點西轩。數(shù)據(jù)庫系統(tǒng)的設(shè)計者巧妙利用了磁盤預(yù)讀原理,將一個節(jié)點的大小設(shè)為等于一個頁脑沿,這樣每個節(jié)點只需要一次I/O就可以完全載入藕畔。為了達到這個目的,在實際實現(xiàn)B-Tree還需要使用如下技巧:
- 每次新建節(jié)點時庄拇,直接申請一個頁的空間注服,這樣就保證一個節(jié)點物理上也存儲在一個頁里,加之計算機存儲分配都是按頁對齊的措近,就實現(xiàn)了一個node只需一次I/O溶弟。
B-Tree中一次檢索最多需要h-1次I/O(根節(jié)點常駐內(nèi)存),漸進復(fù)雜度為O(h)=O(logdN)瞭郑。一般實際應(yīng)用中辜御,出度d是非常大的數(shù)字,通常超過100屈张,因此h非常星苋ā(通常不超過3)。綜上所述阁谆,用B-Tree作為索引結(jié)構(gòu)效率是非常高的菜拓。
而紅黑樹這種結(jié)構(gòu),h明顯要深的多笛厦。由于邏輯上很近的節(jié)點(父子)物理上可能很遠纳鼎,無法利用局部性,所以紅黑樹的I/O漸進復(fù)雜度也為O(h)裳凸,效率明顯比B-Tree差很多贱鄙。
上文還說過,B+Tree更適合外存索引姨谷,原因和內(nèi)節(jié)點出度d有關(guān)逗宁。從上面分析可以看到,d越大索引的性能越好梦湘,而出度的上限取決于節(jié)點內(nèi)key和data的大邢箍拧:
dmax = floor(pagesize / (keysize + datasize + pointsize)) (pagesize – dmax >= pointsize)
或
dmax = floor(pagesize / (keysize + datasize + pointsize)) – 1 (pagesize – dmax < pointsize)
floor表示向下取整件甥。由于B+Tree內(nèi)節(jié)點去掉了data域,因此可以擁有更大的出度哼拔,擁有更好的性能引有。
MySQL索引實現(xiàn)
在MySQL中,索引屬于存儲引擎級別的概念倦逐,不同存儲引擎對索引的實現(xiàn)方式是不同的譬正,本文主要討論MyISAM和InnoDB兩個存儲引擎的索引實現(xiàn)方式。
MyISAM索引實現(xiàn)
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)檬姥,葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址曾我。下圖是MyISAM索引的原理圖:
這里設(shè)表一共有三列,假設(shè)我們以Col1為主鍵健民,則上圖是一個MyISAM表的主索引(Primary key)示意抒巢。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址秉犹。在MyISAM中蛉谜,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別,只是主索引要求key是唯一的凤优,而輔助索引的key可以重復(fù)悦陋。如果我們在Col2上建立一個輔助索引蜈彼,則此索引的結(jié)構(gòu)如下圖所示:
同樣也是一棵B+Tree筑辨,data域保存數(shù)據(jù)記錄的地址。因此幸逆,MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引棍辕,如果指定的Key存在,則取出其data域的值还绘,然后以data域的值為地址楚昭,讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做“非聚集”的拍顷,之所以這么稱呼是為了與InnoDB的聚集索引區(qū)分抚太。
InnoDB索引實現(xiàn)
雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu),但具體實現(xiàn)方式卻與MyISAM截然不同昔案。
-
第一個重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件尿贫。從上文知道,MyISAM索引文件和數(shù)據(jù)文件是分離的踏揣,索引文件僅保存數(shù)據(jù)記錄的地址庆亡。而在InnoDB中,表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)捞稿,這棵樹的葉節(jié)點data域保存了完整的數(shù)據(jù)記錄又谋。這個索引的key是數(shù)據(jù)表的主鍵拼缝,因此InnoDB表數(shù)據(jù)文件本身就是主索引。
InnoDB主索引(同時也是數(shù)據(jù)文件)的示意圖
上圖是InnoDB主索引(同時也是數(shù)據(jù)文件)的示意圖彰亥,可以看到葉節(jié)點包含了完整的數(shù)據(jù)記錄咧七,這種索引叫做聚集索引。因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集剩愧,所以InnoDB要求表必須有主鍵(MyISAM可以沒有)猪叙,如果沒有顯式指定,則MySQL系統(tǒng)會自動選擇一個可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵仁卷,如果不存在這種列穴翩,則MySQL自動為InnoDB表生成一個隱含字段作為主鍵,這個字段長度為6個字節(jié)锦积,類型為長整形芒帕。 -
第二個與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。換句話說丰介,InnoDB的所有輔助索引都引用主鍵作為data域背蟆。
InnoDB輔助索引
這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚集索引這種實現(xiàn)方式使得按主鍵的搜索十分高效哮幢,但是輔助索引搜索需要檢索兩遍索引:首先檢索輔助索引獲得主鍵带膀,然后用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助橙垢,例如知道了InnoDB的索引實現(xiàn)后垛叨,就很容易明白為什么不建議使用過長的字段作為主鍵,因為所有輔助索引都引用主索引柜某,過長的主索引會令輔助索引變得過大嗽元。再例如,用非單調(diào)的字段作為主鍵在InnoDB中不是個好主意喂击,因為InnoDB數(shù)據(jù)文件本身是一顆B+Tree剂癌,非單調(diào)的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整,十分低效翰绊,而使用自增字段作為主鍵則是一個很好的選擇佩谷。
InnoDB的主鍵選擇與插入優(yōu)化
在使用InnoDB存儲引擎時,如果沒有特別的需要监嗜,請永遠使用一個與業(yè)務(wù)無關(guān)的自增字段作為主鍵谐檀。
上文討論過InnoDB的索引實現(xiàn),InnoDB使用聚集索引秤茅,數(shù)據(jù)記錄本身被存于主索引(一顆B+Tree)的葉子節(jié)點上稚补。這就要求同一個葉子節(jié)點內(nèi)(大小為一個內(nèi)存頁或磁盤頁)的各條數(shù)據(jù)記錄按主鍵順序存放,因此每當(dāng)有一條新的記錄插入時框喳,MySQL會根據(jù)其主鍵將其插入適當(dāng)?shù)墓?jié)點和位置课幕,如果頁面達到裝載因子(InnoDB默認(rèn)為15/16)厦坛,則開辟一個新的頁(節(jié)點)。
如果表使用自增主鍵乍惊,那么每次插入新的記錄杜秸,記錄就會順序添加到當(dāng)前索引節(jié)點的后續(xù)位置,當(dāng)一頁寫滿润绎,就會自動開辟一個新的頁撬碟。如下圖所示:
這樣就會形成一個緊湊的索引結(jié)構(gòu),近似順序填滿莉撇。由于每次插入時也不需要移動已有數(shù)據(jù)呢蛤,因此效率很高,也不會增加很多開銷在維護索引上棍郎。
如果使用非自增主鍵(如果身份證號或?qū)W號等)其障,由于每次插入主鍵的值近似于隨機,因此每次新紀(jì)錄都要被插到現(xiàn)有索引頁得中間某個位置:
此時MySQL不得不為了將新記錄插到合適位置而移動數(shù)據(jù)涂佃,甚至目標(biāo)頁面可能已經(jīng)被回寫到磁盤上而從緩存中清掉励翼,此時又要從磁盤上讀回來,這增加了很多開銷辜荠,同時頻繁的移動汽抚、分頁操作造成了大量的碎片,得到了不夠緊湊的索引結(jié)構(gòu)伯病,后續(xù)不得不通過OPTIMIZE TABLE來重建表并優(yōu)化填充頁面造烁。
因此,請盡量在InnoDB上采用自增字段做主鍵狱从。
主索引和輔助索引對比
主索引鍵不允許重復(fù)膨蛮,輔助索引鍵允許重復(fù)
主索引是稀疏索引叠纹,輔助索引是稠密索引
主索引索引的順序就是數(shù)據(jù)的物理存儲順序季研,而輔助索引索引順序與物理存儲順序不同
主索引可以在B+樹的葉節(jié)點上直接找到數(shù)據(jù)且對主鍵的排序查找和范圍查找很快,而輔助索引搜索需要檢索兩遍索引誉察,首先檢索輔助索引獲得主鍵与涡,然后用主鍵到主索引中檢索獲得記錄(對于InnoDB而言)
輔助索引適用于聚集文件,假設(shè)關(guān)系R和關(guān)系S存在多對一的關(guān)系持偏,當(dāng)需要將關(guān)系R中每一個元組和關(guān)系S中每一個元組存在一起驼卖,就需要輔助索引
聚集索引的優(yōu)點
可以將相關(guān)數(shù)據(jù)保存在一起
例如實現(xiàn)電子郵箱時,可以根據(jù)用戶ID來聚集數(shù)據(jù)鸿秆,這樣只需要從磁盤讀取少量的數(shù)據(jù)頁就能獲取某個用戶的全部郵件酌畜。如果沒有使用聚集索引,則每封郵件可能導(dǎo)致一次IO數(shù)據(jù)訪問更快
聚集索引將數(shù)據(jù)和索引放在同一個B-Tree中卿叽,因此獲取數(shù)據(jù)速度更快使用覆蓋索引掃描的查詢可以直接舒勇葉節(jié)點的主鍵值
聚集索引的缺點
聚集數(shù)據(jù)極大提高了IO密集型應(yīng)用的性能桥胞,但如果數(shù)據(jù)全部放在內(nèi)存中恳守,則聚集索引會失去優(yōu)勢
插入速度嚴(yán)重依賴于插入順序。按照主鍵的順序插入是加載數(shù)據(jù)到InnoDB最快的方式贩虾。但如果不是按照主鍵的順序加載催烘,那么在加載完成后最好使用OPTIMIZE TABLE 命令重新組織表
更新聚集索引的代價很高
聚集索引的表在插入新行,或者主鍵被更新需要移動的時候缎罢,可能面臨頁分裂的問題
聚族索引可能導(dǎo)致全表掃描變慢
二級索引(非聚集索引)可能比想象中的大伊群,因為二級索引的葉子結(jié)點包含了主鍵,這也是為何主鍵不能過長的原因
二級索引訪問數(shù)據(jù)需要兩次索引查找
參考文章
MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
數(shù)據(jù)庫系統(tǒng)實現(xiàn)