MySQL索引簡述--BTree索引

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):

  1. d為大于1的一個正整數(shù),稱為B-Tree的度而涉。
  2. h為一個正整數(shù)著瓶,稱為B-Tree的高度。
  3. 每個非葉子節(jié)點由n-1個key和n個指針組成啼县,其中d<=n<=2d材原。
  4. 每個葉子節(jié)點最少包含一個key和兩個指針,最多包含2d-1個key和2d個指針季眷,葉節(jié)點的指針均為null 余蟹。
  5. 所有葉節(jié)點具有相同的深度,等于樹高h子刮。
  6. key和指針互相間隔威酒,節(jié)點兩端是指針窑睁。
  7. 一個節(jié)點中的key從左到右非遞減排列。
  8. 所有節(jié)點組成樹結(jié)構(gòu)葵孤。
  9. 每個指針要么為null担钮,要么指向另外一個節(jié)點。

B-Tree示意圖

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有以下不同點:

  1. 每個節(jié)點的指針上限為2d而不是2d+1司澎。
  2. 內(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)方式是不同的譬正,本文主要討論MyISAMInnoDB兩個存儲引擎的索引實現(xiàn)方式。

MyISAM索引實現(xiàn)

MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)檬姥,葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址曾我。下圖是MyISAM索引的原理圖:

MyISAM主索引結(jié)構(gòu)

這里設(shè)表一共有三列,假設(shè)我們以Col1為主鍵健民,則上圖是一個MyISAM表的主索引(Primary key)示意抒巢。可以看出MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址秉犹。在MyISAM中蛉谜,主索引和輔助索引(Secondary key)在結(jié)構(gòu)上沒有任何區(qū)別,只是主索引要求key是唯一的凤优,而輔助索引的key可以重復(fù)悦陋。如果我們在Col2上建立一個輔助索引蜈彼,則此索引的結(jié)構(gòu)如下圖所示:
MyISAM輔助索引結(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)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末策精,一起剝皮案震驚了整個濱河市舰始,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌咽袜,老刑警劉巖蔽午,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異酬蹋,居然都是意外死亡及老,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門范抓,熙熙樓的掌柜王于貴愁眉苦臉地迎上來骄恶,“玉大人,你說我怎么就攤上這事匕垫∩常” “怎么了?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵象泵,是天一觀的道長寞秃。 經(jīng)常有香客問我,道長偶惠,這世上最難降的妖魔是什么春寿? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮忽孽,結(jié)果婚禮上绑改,老公的妹妹穿的比我還像新娘。我一直安慰自己兄一,他們只是感情好厘线,可當(dāng)我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著出革,像睡著了一般造壮。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上骂束,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天耳璧,我揣著相機與錄音硝全,去河邊找鬼。 笑死楞抡,一個胖子當(dāng)著我的面吹牛伟众,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播召廷,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼凳厢,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了竞慢?” 一聲冷哼從身側(cè)響起先紫,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎筹煮,沒想到半個月后遮精,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡败潦,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年本冲,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片劫扒。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡坞笙,死狀恐怖励两,靈堂內(nèi)的尸體忽然破棺而出微宝,到底是詐尸還是另有隱情废赞,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布贤旷,位于F島的核電站广料,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏幼驶。R本人自食惡果不足惜艾杏,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望县遣。 院中可真熱鬧糜颠,春花似錦汹族、人聲如沸萧求。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽夸政。三九已至,卻和暖如春榴徐,著一層夾襖步出監(jiān)牢的瞬間守问,已是汗流浹背匀归。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留耗帕,地道東北人穆端。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像仿便,于是被迫代替她去往敵國和親体啰。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容