天道不一定酬所有勤
但是,天道只酬勤

天津11选5吧:MySQL索引完全解讀

開發十年,就只剩下這套架構體系了??!

天津11选5蛋托玩法 www.ijudhr.com.cn 索引這個詞,相信大多數人已經相當熟悉了。不過為了文章的完整性,這里再啰嗦一下。索引是一種數據結構,用于幫助我們在大量數據中快速定位到我們想要查找的數據。 索引最形象的比喻就是圖書的目錄了。 注意這里的大量,數據量大了索引才顯得有意義,如果我想要在[1,2,3,4]中找到4這個數據,直接對全數據檢索也很快,沒有必要費力氣建索引再去查找。 索引在mysql數據庫中分三類:
1. B+樹索引 2. Hash索引 3. 全文索引

我們今天要介紹的是工作開發中最常接觸到innodb存儲引擎中的的B+樹索引。

2.二查找叉樹、平衡二叉樹、B樹、B+樹

要介紹B+樹索引,就不得不提二叉查找樹,平衡二叉樹和B樹這三種數據結構。B+樹就是從他們仨演化來的。

2.1 二叉查找樹

首先,讓我們先看一張圖

?

從圖中可以看到,我們為user表(用戶信息表)建立了一個二叉查找樹的索引。圖中的圓為二叉查找樹的節點,節點中存儲了鍵(key)和數據(data)。鍵對應user表中的id,數據對應user表中的行數據。二叉查找樹的特點就是任何節點的左子節點的鍵值都小于當前節點的鍵值,右子節點的鍵值都大于當前節點的鍵值。 頂端的節點我們稱為根節點,沒有子節點的節點我們稱之為葉節點。
如果我們需要查找id=12的用戶信息,利用我們創建的二叉查找樹索引,查找流程如下: 1. 將根節點作為當前節點,把12與當前節點的鍵值10比較,12大于10,接下來我們把當前節點>的右子節點作為當前節點。 2. 繼續把12和當前節點的鍵值13比較,發現12小于13,把當前節點的左子節點作為當前節點。 3. 把12和當前節點的鍵值12對比,12等于12,滿足條件,我們從當前節點中取出data,即id=1>2,name=xm。

利用二叉查找樹我們只需要3次即可找到匹配的數據。如果在表中一條條的查找的話,我們需要6次才能找到。

2.2 平衡二叉樹

上面我們講解了利用二叉查找樹可以快速的找到數據。但是,如果上面的二叉查找樹是這樣的構造:

?

這個時候可以看到我們的二叉查找樹變成了一個鏈表。如果我們需要查找id=17的用戶信息,我們需要查找7次,也就相當于全表掃描了。 導致這個現象的原因其實是二叉查找樹變得不平衡了,也就是高度太高了,從而導致查找效率的不穩定。 為了解決這個問題,我們需要保證二叉查找樹一直保持平衡,就需要用到平衡二叉樹了。
平衡二叉樹又稱AVL樹,在滿足二叉查找樹特性的基礎上,要求每個節點的左右子樹的高度不能超過1。 下面是平衡二叉樹和非平衡二叉樹的對比: ?

由平衡二叉樹的構造我們可以發現第一張圖中的二叉樹其實就是一棵平衡二叉樹。平衡二叉樹保證了樹的構造是平衡的,當我們插入或刪除數據導致不滿足平衡二叉樹不平衡時,平衡二叉樹會進行調整樹上的節點來保持平衡。具體的調整方式這里就不介紹了。平衡二叉樹相比于二叉查找樹來說,查找效率更穩定,總體的查找速度也更快。

2.3 B樹

因為內存的易失性。一般情況下,我們都會選擇將user表中的數據和索引存儲在磁盤這種外圍設備中。但是和內存相比,從磁盤中讀取數據的速度會慢上百倍千倍甚至萬倍,所以,我們應當盡量減少從磁盤中讀取數據的次數。 另外,從磁盤中讀取數據時,都是按照磁盤塊來讀取的,并不是一條一條的讀。 如果我們能把盡量多的數據放進磁盤塊中,那一次磁盤讀取操作就會讀取更多數據,那我們查找數據的時間也會大幅度降低。 如果我們用樹這種數據結構作為索引的數據結構,那我們每查找一次數據就需要從磁盤中讀取一個節點,也就是我們說的一個磁盤塊,我們都知道平衡二叉樹可是每個節點只存儲一個鍵值和數據的。那說明什么?說明每個磁盤塊僅僅存儲一個鍵值和數據!那如果我們要存儲海量的數據呢?可以想象到二叉樹的節點將會非常多,高度也會及其高,我們查找數據時也會進行很多次磁盤IO,我們查找數據的效率將會極低!

?

為了解決平衡二叉樹的這個弊端,我們應該尋找一種單個節點可以存儲多個鍵值和數據的平衡樹。也就是我們接下來要說的B樹。
B樹(Balance Tree)即為平衡樹的意思,下圖即是一顆B樹。

?

注意:
– 圖中的p節點為指向子節點的指針,二叉查找樹和平衡二叉樹其實也有,因為圖的美觀性,被省略了。 – 圖中的每個節點稱為頁,頁就是我們上面說的磁盤塊,在mysql中數據讀取的基本單位都是頁,所以我們這里叫做頁更符合mysql中索引的底層數據結構。

從上圖可以看出,B樹相對于平衡二叉樹,每個節點存儲了更多的鍵值(key)和數據(data),并且每個節點擁有更多的子節點,子節點的個數一般稱為階,上述圖中的B樹為3階B樹,高度也會很低。 基于這個特性,B樹查找數據讀取磁盤的次數將會很少,數據的查找效率也會比平衡二叉樹高很多。
假如我們要查找id=28的用戶信息,那么我們在上圖B樹中查找的流程如下: 1. 先找到根節點也就是頁1,判斷28在鍵值17和35之間,我們那么我們根據頁1中的指針p2找到頁3。 2. 將28和頁3中的鍵值相比較,28在26和30之間,我們根據頁3中的指針p2找到頁8。 3. 將28和頁8中的鍵值相比較,發現有匹配的鍵值28,鍵值28對應的用戶信息為(28,bv)。

注意: – B樹的構造是有一些規定的,但這不是本文的關注點,有興趣的同學可以令行了解。 – B樹也是平衡的,當增加或刪除數據而導致B樹不平衡時,也是需要進行節點調整的。

2.4 B+樹

B+樹是對B樹的進一步優化。讓我們先來看下B+樹的結構圖:

Hollis為了防爬蟲以及未經授權的惡意轉載,此處內容已被作者隱藏,請輸入驗證碼查看內容
驗證碼:
請關注本站微信公眾號,回復“驗證碼”,獲取驗證碼。在微信里搜索“Hollis”或者“hollischuang”或者微信掃描右側二維碼都可以關注本站微信公眾號。

(全文完) 歡迎關注『Java之道』微信公眾號
贊(1)
如未加特殊說明,此網站文章均為原創,轉載必須注明出處。天津11选5蛋托玩法 » MySQL索引完全解讀
分享到: 更多 (0)

評論 1

  • 昵稱 (必填)
  • 郵箱 (必填)
  • 網址
  1. #1

    期待

    王馬3周前 (11-18)回復

HollisChuang's Blog

聯系我關于我