真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?-創(chuàng)新互聯(lián)

二叉樹(shù)(Binary Search Trees)

二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱作“左子樹(shù)”(Left Subtree)和“右子樹(shù)”(Right Subtree)。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。

10年積累的成都網(wǎng)站制作、成都網(wǎng)站建設(shè)經(jīng)驗(yàn),可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你,你也不認(rèn)識(shí)我。但先做網(wǎng)站后付款的網(wǎng)站建設(shè)流程,更有敘永免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

二叉樹(shù)有如下特性:

  • 每個(gè)結(jié)點(diǎn)都包含一個(gè)元素以及 n 個(gè)子樹(shù),這里 0≤n≤2。?

  • 左子樹(shù)和右子樹(shù)是有順序的,次序不能任意顛倒。左子樹(shù)的值要小于父結(jié)點(diǎn),右子樹(shù)的值要大于父結(jié)點(diǎn)。

光看概念有點(diǎn)枯燥,假設(shè)我們現(xiàn)在有這樣一組數(shù)[35 27 48 12 29 38 55],順序的插入到一個(gè)數(shù)的結(jié)構(gòu)中,步驟如下 :

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

好了,這就是一棵二叉樹(shù)啦!我們能看到,經(jīng)過(guò)一系列的插入操作之后,原本無(wú)序的一組數(shù)已經(jīng)變成一個(gè)有序的結(jié)構(gòu)了,并且這個(gè)樹(shù)滿足了上面提到的兩個(gè)二叉樹(shù)的特性!

但是如果同樣是上面那一組數(shù),我們自己升序排列后再插入,也就是說(shuō)按照[12 27 29 35 38 48 55]的順序插入,會(huì)怎么樣呢?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

由于是升序插入,新插入的數(shù)據(jù)總是比已存在的結(jié)點(diǎn)數(shù)據(jù)都要大,所以每次都會(huì)往結(jié)點(diǎn)的右邊插入,最終導(dǎo)致這棵樹(shù)嚴(yán)重偏科!

上圖就是最壞的情況,也就是一棵樹(shù)退化為一個(gè)線性鏈表了,這樣查找效率自然就低了,完全沒(méi)有發(fā)揮樹(shù)的優(yōu)勢(shì)了呢!?

為了較大發(fā)揮二叉樹(shù)的查找效率,讓二叉樹(shù)不再偏科,保持各科平衡,所以有了平衡二叉樹(shù)!

平衡二叉樹(shù) (AVL Trees)

平衡二叉樹(shù)是一種特殊的二叉樹(shù),所以他也滿足前面說(shuō)到的二叉樹(shù)的兩個(gè)特性,同時(shí)還有一個(gè)特性:它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1,并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

大家也看到了前面[35 27 48 12 29 38 55]插入完成后的圖,其實(shí)就已經(jīng)是一棵平衡二叉樹(shù)啦。

那如果按照[12 27 29 35 38 48 55]的順序插入一棵平衡二叉樹(shù),會(huì)怎么樣呢?

我們看看插入以及平衡的過(guò)程:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

這棵樹(shù)始終滿足平衡二叉樹(shù)的幾個(gè)特性而保持平衡!這樣我們的樹(shù)也不會(huì)退化為線性鏈表了!

我們需要查找一個(gè)數(shù)的時(shí)候就能沿著樹(shù)根一直往下找,這樣的查找效率和二分法查找是一樣的呢!

一棵平衡二叉樹(shù)能容納多少的結(jié)點(diǎn)呢?這跟樹(shù)的高度是有關(guān)系的,假設(shè)樹(shù)的高度為 h,那每一層最多容納的結(jié)點(diǎn)數(shù)量為 2^(n-1),整棵樹(shù)最多容納節(jié)點(diǎn)數(shù)為 2^0+2^1+2^2+...+2^(h-1)。

這樣計(jì)算,100w 數(shù)據(jù)樹(shù)的高度大概在 20 左右,也就是說(shuō)從有著 100w 條數(shù)據(jù)的平衡二叉樹(shù)中找一個(gè)數(shù)據(jù),最壞的情況下需要 20 次查找。

如果是內(nèi)存操作,效率也是很高的!但是我們數(shù)據(jù)庫(kù)中的數(shù)據(jù)基本都是放在磁盤(pán)中的,每讀取一個(gè)二叉樹(shù)的結(jié)點(diǎn)就是一次磁盤(pán) IO,這樣我們找一條數(shù)據(jù)如果要經(jīng)過(guò) 20?次磁盤(pán)的 IO?

那性能就成了一個(gè)很大的問(wèn)題了!那我們是不是可以把這棵樹(shù)壓縮一下,讓每一層能夠容納更多的節(jié)點(diǎn)呢?雖然我矮,但是我胖啊...

B-Tree

這顆矮胖的樹(shù)就是 B-Tree,注意中間是杠精的杠而不是減,所以也不要讀成 B 減 Tree 了~

那 B-Tree 有哪些特性呢?一棵 m 階的 B-Tree 有如下特性:

  • 每個(gè)結(jié)點(diǎn)最多 m 個(gè)子結(jié)點(diǎn)。?

  • 除了根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)最少有 m/2(向上取整)個(gè)子結(jié)點(diǎn)。?

  • 如果根結(jié)點(diǎn)不是葉子結(jié)點(diǎn),那根結(jié)點(diǎn)至少包含兩個(gè)子結(jié)點(diǎn)。?

  • 所有的葉子結(jié)點(diǎn)都位于同一層。?

  • 每個(gè)結(jié)點(diǎn)都包含 k 個(gè)元素(關(guān)鍵字),這里 m/2≤k。

  • 每個(gè)節(jié)點(diǎn)中的元素(關(guān)鍵字)從小到大排列。?

  • 每個(gè)元素(關(guān)鍵字)字左結(jié)點(diǎn)的值,都小于或等于該元素(關(guān)鍵字)。右結(jié)點(diǎn)的值都大于或等于該元素(關(guān)鍵字)。

是不是感覺(jué)跟丈母娘張口問(wèn)你要彩禮一樣,列一堆的條件,而且每一條都讓你很懵逼!

下面我們以一個(gè)[0,1,2,3,4,5,6,7]的數(shù)組插入一棵 3 階的 B-Tree 為例,將所有的條件都串起來(lái),你就明白了!

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

那么,你是否對(duì) B-Tree 的幾點(diǎn)特性都清晰了呢?在二叉樹(shù)中,每個(gè)結(jié)點(diǎn)只有一個(gè)元素。

但是在 B-Tree 中,每個(gè)結(jié)點(diǎn)都可能包含多個(gè)元素,并且非葉子結(jié)點(diǎn)在元素的左右都有指向子結(jié)點(diǎn)的指針。

如果需要查找一個(gè)元素,那流程是怎么樣的呢?我們看下圖,如果我們要在下面的 B-Tree 中找到關(guān)鍵字 24,那流程如下:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

從這個(gè)流程我們能看出,B-Tree 的查詢效率好像也并不比平衡二叉樹(shù)高。但是查詢所經(jīng)過(guò)的結(jié)點(diǎn)數(shù)量要少很多,也就意味著要少很多次的磁盤(pán) IO,這對(duì)性能的提升是很大的。

從前面對(duì) B-Tree 操作的圖,我們能看出來(lái),元素就是類似 1、2、3 這樣的數(shù)值。

但是數(shù)據(jù)庫(kù)的數(shù)據(jù)都是一條條的數(shù)據(jù),如果某個(gè)數(shù)據(jù)庫(kù)以 B-Tree 的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù),那數(shù)據(jù)怎么存放的呢?

我們看下一張圖:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

普通的 B-Tree 的結(jié)點(diǎn)中,元素就是一個(gè)個(gè)的數(shù)字。但是上圖中,我們把元素部分拆分成了 key-data 的形式,Key 就是數(shù)據(jù)的主鍵,Data 就是具體的數(shù)據(jù)。

這樣我們?cè)谡乙粭l數(shù)的時(shí)候,就沿著根結(jié)點(diǎn)往下找就 OK 了,效率是比較高的。

B+Tree

B+Tree 是在 B-Tree 基礎(chǔ)上的一種優(yōu)化,使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)。

B+Tree 與 B-Tree 的結(jié)構(gòu)很像,但是也有幾個(gè)自己的特性:

  • 所有的非葉子節(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字信息。?

  • 所有衛(wèi)星數(shù)據(jù)(具體數(shù)據(jù))都存在葉子結(jié)點(diǎn)中。?

  • 所有的葉子結(jié)點(diǎn)中包含了全部元素的信息。?

  • 所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針。

如果上面 B-Tree 的圖變成 B+Tree,那應(yīng)該如下:?

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

大家仔細(xì)對(duì)比于 B-Tree 的圖能發(fā)現(xiàn)什么不同?

  • 非葉子結(jié)點(diǎn)上已經(jīng)只有 Key 信息了,滿足上面第 1 點(diǎn)特性!?

  • 所有葉子結(jié)點(diǎn)下面都有一個(gè) Data 區(qū)域,滿足上面第 2 點(diǎn)特性!?

  • 非葉子結(jié)點(diǎn)的數(shù)據(jù)在葉子結(jié)點(diǎn)上都能找到,如根結(jié)點(diǎn)的元素 4、8 在最底層的葉子結(jié)點(diǎn)上也能找到,滿足上面第 3 點(diǎn)特性!?

  • 注意圖中葉子結(jié)點(diǎn)之間的箭頭,滿足上面第 4 點(diǎn)特性!

B-Tree or B+Tree?

在講這兩種數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)庫(kù)中的選擇之前,我們還需要了解的一個(gè)知識(shí)點(diǎn)是操作系統(tǒng)從磁盤(pán)讀取數(shù)據(jù)到內(nèi)存是以磁盤(pán)塊(Block)為基本單位的,位于同一個(gè)磁盤(pán)塊中的數(shù)據(jù)會(huì)被一次性讀取出來(lái),而不是需要什么取什么。

即使只需要一個(gè)字節(jié),磁盤(pán)也會(huì)從這個(gè)位置開(kāi)始,順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。

這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理:當(dāng)一個(gè)數(shù)據(jù)被用到時(shí),其附近的數(shù)據(jù)也通常會(huì)馬上被使用。?

預(yù)讀的長(zhǎng)度一般為頁(yè)(Page)的整倍數(shù)。頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊,硬件及操作系統(tǒng)往往將主存和磁盤(pán)存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊,每個(gè)存儲(chǔ)塊稱為一頁(yè)(在許多操作系統(tǒng)中,頁(yè)的大小通常為 4K)。

B-Tree 和 B+Tree 該如何選擇呢?都有哪些優(yōu)劣呢?

①B-Tree 因?yàn)榉侨~子結(jié)點(diǎn)也保存具體數(shù)據(jù),所以在查找某個(gè)關(guān)鍵字的時(shí)候找到即可返回。

而 B+Tree 所有的數(shù)據(jù)都在葉子結(jié)點(diǎn),每次查找都得到葉子結(jié)點(diǎn)。所以在同樣高度的 B-Tree 和 B+Tree 中,B-Tree 查找某個(gè)關(guān)鍵字的效率更高。?

②由于 B+Tree 所有的數(shù)據(jù)都在葉子結(jié)點(diǎn),并且結(jié)點(diǎn)之間有指針連接,在找大于某個(gè)關(guān)鍵字或者小于某個(gè)關(guān)鍵字的數(shù)據(jù)的時(shí)候,B+Tree 只需要找到該關(guān)鍵字然后沿著鏈表遍歷就可以了,而 B-Tree 還需要遍歷該關(guān)鍵字結(jié)點(diǎn)的根結(jié)點(diǎn)去搜索。?

③由于 B-Tree 的每個(gè)結(jié)點(diǎn)(這里的結(jié)點(diǎn)可以理解為一個(gè)數(shù)據(jù)頁(yè))都存儲(chǔ)主鍵+實(shí)際數(shù)據(jù),而 B+Tree 非葉子結(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字信息,而每個(gè)頁(yè)的大小是有限的,所以同一頁(yè)能存儲(chǔ)的 B-Tree 的數(shù)據(jù)會(huì)比 B+Tree 存儲(chǔ)的更少。

這樣同樣總量的數(shù)據(jù),B-Tree 的深度會(huì)更大,增大查詢時(shí)的磁盤(pán) I/O 次數(shù),進(jìn)而影響查詢效率。?

鑒于以上的比較,所以在常用的關(guān)系型數(shù)據(jù)庫(kù)中,都是選擇 B+Tree 的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)!

下面我們以 MySQL 的 InnoDB 存儲(chǔ)引擎為例講解,其他類似 SQL Server、Oracle 的原理!

InnoDB?引擎數(shù)據(jù)存儲(chǔ)

在 InnoDB 存儲(chǔ)引擎中,也有頁(yè)的概念,默認(rèn)每個(gè)頁(yè)的大小為 16K,也就是每次讀取數(shù)據(jù)時(shí)都是讀取 4*4K 的大??!

假設(shè)我們現(xiàn)在有一個(gè)用戶表,我們往里面寫(xiě)數(shù)據(jù):

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

這里需要注意的一點(diǎn)是,在某個(gè)頁(yè)內(nèi)插入新行時(shí),為了減少數(shù)據(jù)的移動(dòng),通常是插入到當(dāng)前行的后面或者是已刪除行留下來(lái)的空間,所以在某一個(gè)頁(yè)內(nèi)的數(shù)據(jù)并不是完全有序的(后面頁(yè)結(jié)構(gòu)部分有細(xì)講)。

但是為了數(shù)據(jù)訪問(wèn)順序性,在每個(gè)記錄中都有一個(gè)指向下一條記錄的指針,以此構(gòu)成了一條單向有序鏈表,不過(guò)在這里為了方便演示我是按順序排列的!

由于數(shù)據(jù)還比較少,一個(gè)頁(yè)就能容下,所以只有一個(gè)根結(jié)點(diǎn),主鍵和數(shù)據(jù)也都是保存在根結(jié)點(diǎn)(左邊的數(shù)字代表主鍵,右邊名字、性別代表具體的數(shù)據(jù))。

假設(shè)我們寫(xiě)入 10 條數(shù)據(jù)之后,Page1 滿了,再寫(xiě)入新的數(shù)據(jù)會(huì)怎么存放呢?

我們繼續(xù)看下圖:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

有個(gè)叫“秦壽生”的朋友來(lái)了,但是 Page1 已經(jīng)放不下數(shù)據(jù)了,這時(shí)候就需要進(jìn)行頁(yè)分裂,產(chǎn)生一個(gè)新的 Page。

在 InnoDB 中的流程是怎么樣的呢?

  • 產(chǎn)生新的 Page2,然后將 Page1 的內(nèi)容復(fù)制到 Page2。?

  • 產(chǎn)生新的 Page3,“秦壽生”的數(shù)據(jù)放入 Page3。?

  • 原來(lái)的 Page1 依然作為根結(jié)點(diǎn),但是變成了一個(gè)不存放數(shù)據(jù)只存放索引的頁(yè),并且有兩個(gè)子結(jié)點(diǎn) Page2、Page3。

這里有兩個(gè)問(wèn)題需要注意的是:

①為什么要復(fù)制 Page1 為 Page2 而不是創(chuàng)建一個(gè)新的頁(yè)作為根結(jié)點(diǎn),這樣就少了一步復(fù)制的開(kāi)銷了?

如果是重新創(chuàng)建根結(jié)點(diǎn),那根結(jié)點(diǎn)存儲(chǔ)的物理地址可能經(jīng)常會(huì)變,不利于查找。

并且在 InnoDB 中根結(jié)點(diǎn)是會(huì)預(yù)讀到內(nèi)存中的,所以結(jié)點(diǎn)的物理地址固定會(huì)比較好!

②原來(lái) Page1 有 10?條數(shù)據(jù),在插入第 11 條數(shù)據(jù)的時(shí)候進(jìn)行裂變,根據(jù)前面對(duì) B-Tree、B+Tree 特性的了解,那這至少是一棵 11 階的樹(shù),裂變之后每個(gè)結(jié)點(diǎn)的元素至少為 11/2=5 個(gè)。

那是不是應(yīng)該頁(yè)裂變之后主鍵 1-5 的數(shù)據(jù)還是在原來(lái)的頁(yè),主鍵 6-11 的數(shù)據(jù)會(huì)放到新的頁(yè),根結(jié)點(diǎn)存放主鍵 6??

如果是這樣的話,新的頁(yè)空間利用率只有 50%,并且會(huì)導(dǎo)致更為頻繁的頁(yè)分裂。

所以 InnoDB 對(duì)這一點(diǎn)做了優(yōu)化,新的數(shù)據(jù)放入新創(chuàng)建的頁(yè),不移動(dòng)原有頁(yè)面的任何記錄。

隨著數(shù)據(jù)的不斷寫(xiě)入,這棵樹(shù)也逐漸枝繁葉茂,如下圖:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

每次新增數(shù)據(jù),都是將一個(gè)頁(yè)寫(xiě)滿,然后新創(chuàng)建一個(gè)頁(yè)繼續(xù)寫(xiě),這里其實(shí)是有個(gè)隱含條件的,那就是主鍵自增!

主鍵自增寫(xiě)入時(shí)新插入的數(shù)據(jù)不會(huì)影響到原有頁(yè),插入效率高!且頁(yè)的利用率高!

但是如果主鍵是無(wú)序的或者隨機(jī)的,那每次的插入可能會(huì)導(dǎo)致原有頁(yè)頻繁的分裂,影響插入效率!降低頁(yè)的利用率!這也是為什么在 InnoDB 中建議設(shè)置主鍵自增的原因!

這棵樹(shù)的非葉子結(jié)點(diǎn)上存的都是主鍵,那如果一個(gè)表沒(méi)有主鍵會(huì)怎么樣?在 InnoDB 中,如果一個(gè)表沒(méi)有主鍵,那默認(rèn)會(huì)找建了唯一索引的列,如果也沒(méi)有,則會(huì)生成一個(gè)隱形的字段作為主鍵!

有數(shù)據(jù)插入那就有刪除,如果這個(gè)用戶表頻繁的插入和刪除,那會(huì)導(dǎo)致數(shù)據(jù)頁(yè)產(chǎn)生碎片,頁(yè)的空間利用率低,還會(huì)導(dǎo)致樹(shù)變的“虛高”,降低查詢效率!這可以通過(guò)索引重建來(lái)消除碎片提高查詢效率!

InnoDB?引擎數(shù)據(jù)查找

數(shù)據(jù)插入了怎么查找呢?

  • 找到數(shù)據(jù)所在的頁(yè)。這個(gè)查找過(guò)程就跟前面說(shuō)到的 B+Tree 的搜索過(guò)程是一樣的,從根結(jié)點(diǎn)開(kāi)始查找一直到葉子結(jié)點(diǎn)。?

  • 在頁(yè)內(nèi)找具體的數(shù)據(jù)。讀取第 1 步找到的葉子結(jié)點(diǎn)數(shù)據(jù)到內(nèi)存中,然后通過(guò)分塊查找的方法找到具體的數(shù)據(jù)。

這跟我們?cè)谛氯A字典中找某個(gè)漢字是一樣的,先通過(guò)字典的索引定位到該漢字拼音所在的頁(yè),然后到指定的頁(yè)找到具體的漢字。

InnoDB 中定位到頁(yè)后用了哪種策略快速查找某個(gè)主鍵呢?這我們就需要從頁(yè)結(jié)構(gòu)開(kāi)始了解。

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

左邊藍(lán)色區(qū)域稱為 Page Directory,這塊區(qū)域由多個(gè) Slot 組成,是一個(gè)稀疏索引結(jié)構(gòu),即一個(gè)槽中可能屬于多個(gè)記錄,最少屬于 4 條記錄,最多屬于 8 條記錄。

槽內(nèi)的數(shù)據(jù)是有序存放的,所以當(dāng)我們尋找一條數(shù)據(jù)的時(shí)候可以先在槽中通過(guò)二分法查找到一個(gè)大致的位置。

右邊區(qū)域?yàn)閿?shù)據(jù)區(qū)域,每一個(gè)數(shù)據(jù)頁(yè)中都包含多條行數(shù)據(jù)。注意看圖中最上面和最下面的兩條特殊的行記錄 Infimum 和 Supremum,這是兩個(gè)虛擬的行記錄。

在沒(méi)有其他用戶數(shù)據(jù)的時(shí)候 Infimum 的下一條記錄的指針指向 Supremum。

當(dāng)有用戶數(shù)據(jù)的時(shí)候,Infimum 的下一條記錄的指針指向當(dāng)前頁(yè)中最小的用戶記錄,當(dāng)前頁(yè)中大的用戶記錄的下一條記錄的指針指向 Supremum,至此整個(gè)頁(yè)內(nèi)的所有行記錄形成一個(gè)單向鏈表。

行記錄被 Page Directory 邏輯的分成了多個(gè)塊,塊與塊之間是有序的,也就是說(shuō)“4”這個(gè)槽指向的數(shù)據(jù)塊內(nèi)大的行記錄的主鍵都要比“8”這個(gè)槽指向的數(shù)據(jù)塊內(nèi)最小的行記錄的主鍵要小。但是塊內(nèi)部的行記錄不一定有序。

每個(gè)行記錄的都有一個(gè) n_owned 的區(qū)域(圖中粉紅色區(qū)域),n_owned 標(biāo)識(shí)這個(gè)塊有多少條數(shù)據(jù)。

偽記錄 Infimum 的 n_owned 值總是 1,記錄 Supremum 的 n_owned 的取值范圍為[1,8],其他用戶記錄 n_owned 的取值范圍[4,8]。

并且只有每個(gè)塊中大的那條記錄的 n_owned 才會(huì)有值,其他的用戶記錄的 n_owned 為 0。

所以當(dāng)我們要找主鍵為 6 的記錄時(shí),先通過(guò)二分法在稀疏索引中找到對(duì)應(yīng)的槽,也就是 Page Directory 中“8”這個(gè)槽。

“8”這個(gè)槽指向的是該數(shù)據(jù)塊中大的記錄,而數(shù)據(jù)是單向鏈表結(jié)構(gòu),所以無(wú)法逆向查找。

所以需要找到上一個(gè)槽即“4”這個(gè)槽,然后通過(guò)“4”這個(gè)槽中大的用戶記錄的指針沿著鏈表順序查找到目標(biāo)記錄。

聚集索引&非聚集索引

前面關(guān)于數(shù)據(jù)存儲(chǔ)的都是演示的聚集索引的實(shí)現(xiàn),如果上面的用戶表需要以“用戶名字”建立一個(gè)非聚集索引,是怎么實(shí)現(xiàn)的呢?

我們看下圖:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

非聚集索引的存儲(chǔ)結(jié)構(gòu)與前面是一樣的,不同的是在葉子結(jié)點(diǎn)的數(shù)據(jù)部分存的不再是具體的數(shù)據(jù),而是數(shù)據(jù)的聚集索引的 Key。

所以通過(guò)非聚集索引查找的過(guò)程是先找到該索引 Key 對(duì)應(yīng)的聚集索引的 Key,然后再拿聚集索引的 Key 到主鍵索引樹(shù)上查找對(duì)應(yīng)的數(shù)據(jù),這個(gè)過(guò)程稱為回表!

PS:圖中的這些名字均來(lái)源于網(wǎng)絡(luò),希望沒(méi)有誤傷正在看這篇文章的你~^_^

InnoDB 與?MyISAM 引擎對(duì)比

上面包括存儲(chǔ)和搜索都是拿的 InnoDB 引擎為例,那 MyISAM 與 InnoDB 在存儲(chǔ)上有啥不同呢?憋縮話,看圖:

心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?

上圖為 MyISAM 主鍵索引的存儲(chǔ)結(jié)構(gòu),我們能看到的不同是:

  • 主鍵索引樹(shù)的葉子結(jié)點(diǎn)的數(shù)據(jù)區(qū)域沒(méi)有存放實(shí)際的數(shù)據(jù),存放的是數(shù)據(jù)記錄的地址。?

  • 數(shù)據(jù)的存儲(chǔ)不是按主鍵順序存放的,是按寫(xiě)入的順序存放。

也就是說(shuō) InnoDB 引擎數(shù)據(jù)在物理上是按主鍵順序存放,而 MyISAM 引擎數(shù)據(jù)在物理上按插入的順序存放。

并且 MyISAM 的葉子結(jié)點(diǎn)不存放數(shù)據(jù),所以非聚集索引的存儲(chǔ)結(jié)構(gòu)與聚集索引類似,在使用非聚集索引查找數(shù)據(jù)的時(shí)候通過(guò)非聚集索引樹(shù)就能直接找到數(shù)據(jù)的地址了,不需要回表,這比 InnoDB 的搜索效率會(huì)更高呢!

索引優(yōu)化建議

大家經(jīng)常會(huì)在很多的文章或書(shū)中能看到一些索引的使用建議,比如說(shuō):

  • like 的模糊查詢以 % 開(kāi)頭,會(huì)導(dǎo)致索引失效。?

  • 一個(gè)表建的索引盡量不要超過(guò) 5 個(gè)。?

  • 盡量使用覆蓋索引。?

  • 盡量不要在重復(fù)數(shù)據(jù)多的列上建索引。?

  • ......

很多這里就不一一列舉了!那看完這篇文章,我們能否帶著疑問(wèn)去分析一下為什么要有這些建議?

為什么 like 的模糊查詢以 % 開(kāi)頭,會(huì)導(dǎo)致索引失效?為什么一個(gè)表建的索引盡量不要超過(guò) 5 個(gè)?

為什么?為什么??為什么???相信看到這里的你再加上自己的一些思考應(yīng)該有答案了吧?

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內(nèi)外云服務(wù)器15元起步,三天無(wú)理由+7*72小時(shí)售后在線,公司持有idc許可證,提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì),專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。


本文題目:心里沒(méi)點(diǎn)B樹(shù),怎能吃透數(shù)據(jù)庫(kù)索引底層原理?-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源:http://weahome.cn/article/dgdsjs.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部