10張圖帶你輕松理解關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)的工作原理

什么是索引

索引是一種幫助減少數(shù)據(jù)查詢時(shí)間的數(shù)據(jù)結(jié)構(gòu)。索引在實(shí)現(xiàn)這一目標(biāo)時(shí)，需要付出存儲(chǔ)、內(nèi)存和保持更新（較慢的寫(xiě)入速度）的額外成本，這使得我們可以跳過(guò)檢查每一行表的繁瑣任務(wù)。

就像書(shū)后面的索引頁(yè)一樣，它可以幫助你找到正確的一頁(yè)。

為什么需要索引

小量的數(shù)據(jù)是易于管理的(比如一個(gè)小班級(jí)的出勤表), 但是, 當(dāng)數(shù)據(jù)規(guī)模變得更大時(shí)(比如一個(gè)大城市的出生登記), 事情就不那么容易了。之前能夠很快執(zhí)行的操作都開(kāi)始變得緩慢。

想象一下，如果你需要在一頁(yè) A4 紙的名單上上找到某個(gè)信息，與需要在上千頁(yè)的名單中找到它，你的查詢策略會(huì)有何變化。

無(wú)論你想到的查詢策略是什么，幾乎總會(huì)有某個(gè)數(shù)據(jù)庫(kù)在某個(gè)特定的時(shí)間點(diǎn)用到了和你相似的策略，因?yàn)殡S著它們的發(fā)展，他們需要收集和存儲(chǔ)的數(shù)據(jù)會(huì)逐漸變得龐大，最終必將遇到上述的問(wèn)題。

因此，我們需要索引來(lái)幫助我們盡可能快地獲得我們需要的相關(guān)數(shù)據(jù)。

索引是如何工作的？

一般而言,索引越多讀取性能越好,但這是以寫(xiě)性能的降低為代價(jià)的,因?yàn)槟阈枰３謱?duì)索引的更新

其中一個(gè)方案是根據(jù)查詢方式來(lái)維護(hù)數(shù)據(jù)存儲(chǔ)邏輯。比如你需要通過(guò)姓名來(lái)查詢某個(gè)名單，那就將名單按照姓名進(jìn)行排序。但這個(gè)策略有許多問(wèn)題需要考慮:

1. 如果我有多種查詢方式呢？ 比如，既有用姓名查詢也有用身份證查詢。
2. 如果有新數(shù)據(jù)的寫(xiě)入, 寫(xiě)入速度會(huì)受到多大的影響？
3. 如何處理數(shù)據(jù)的更新呢？
4. 所有的數(shù)據(jù)操作的復(fù)雜度是什么樣的呢？

無(wú)論你的原始策略是什么，肯定都需要一種維護(hù)數(shù)據(jù)順序的方式以便獲取相關(guān)的無(wú)序數(shù)據(jù)。

如下表中的例子，幾乎不需要什么時(shí)間，我們就可以通過(guò)掃描整個(gè)表將查詢到我們想要的數(shù)據(jù)。

+─────+─────────+──────────────+
| id  | name    | city         |
+─────+─────────+──────────────+
| 1   | Mahdi   | Ottawa       |
| 2   | Elon    | Mars         |
| 3   | Jeff    | Orbit        |
| 4   | Klay    | Oakland      |
| 5   | Lebron  | Los Angeles  |
+─────+─────────+──────────────+

加入存儲(chǔ)的數(shù)據(jù)規(guī)模無(wú)法全部存放到內(nèi)存，或者需要很長(zhǎng)的時(shí)間才能將數(shù)據(jù)從磁盤(pán)加載到內(nèi)存呢？如下表中，數(shù)據(jù)分散在磁盤(pán)中，無(wú)法完全加載到內(nèi)存。

+──────────+─────────+───────────────────+
| id       | name    | city              |
+──────────+─────────+───────────────────+
| 1        | Mahdi   | Ottawa            |
| 2        | Elon    | Mars              |
| 3        | Jeff    | Orbit             |
| 4        | Klay    | Oakland           |
| 5        | Lebron  | Los Angeles       |
| ...      | ...     | ...               |
| 1000000  | Steph   | San Francisco     |
| 1001000  | Linus   | Portland          |
+───────+─────────+──────────────────────+

大部分 R&D 立刻想到了，我們需要字典(hash表)以及一種可以不需要掃描磁盤(pán)直接定位到正在查詢的指定行的手段。

索引葉子節(jié)點(diǎn)提供指定列到索引的映射，它能夠存儲(chǔ)符合條件的行所在的位置。

RowIDs indexes mapping to table data

這些索引葉子節(jié)點(diǎn)是索引列和相應(yīng)行在磁盤(pán)上的位置之間的映射。它提供了一種通過(guò)索引列來(lái)快速獲取指定行的方法。掃描索引的速度會(huì)更快，因?yàn)樗悄阋阉鞯牧械木o湊表示（更少的字節(jié)）。它為你節(jié)省了讀取一堆塊來(lái)尋找所需數(shù)據(jù)的時(shí)間，而且更便于緩存，進(jìn)一步加快了整個(gè)過(guò)程的速度。

這些索引的葉子節(jié)點(diǎn)是統(tǒng)一大小的，我們?cè)诿總€(gè)塊中盡可能多地存儲(chǔ)這些葉子節(jié)點(diǎn)。由于這種結(jié)構(gòu)需要對(duì)數(shù)據(jù)進(jìn)行排序（邏輯上，而不是磁盤(pán)上的物理排序），我們需要解決必須快速添加和刪除數(shù)據(jù)的問(wèn)題。通常我們用一個(gè)雙向鏈表來(lái)解決這個(gè)問(wèn)題。

這里的好處有兩個(gè)：它允許我們向前和向后讀取索引葉子節(jié)點(diǎn)，并在我們刪除或添加新行時(shí)快速重建索引結(jié)構(gòu)，因?yàn)槲覀冎皇窃谛薷闹羔槨?/p>

由于這些葉子節(jié)點(diǎn)在磁盤(pán)上并不是按順序排列的，我們需要一種方法來(lái)獲得正確的索引葉子節(jié)點(diǎn)。

平衡樹(shù)(B-Tree)

B樹(shù) VS B+樹(shù)

?「B樹(shù) VS B+樹(shù)」

B+樹(shù)主要區(qū)別是，不在中間節(jié)點(diǎn)存儲(chǔ)任何數(shù)據(jù)。所有的數(shù)據(jù)引用都鏈接到葉子節(jié)點(diǎn)上，這樣可以更好地緩存樹(shù)狀結(jié)構(gòu)(中間節(jié)點(diǎn)數(shù)據(jù)規(guī)模小更便于緩存索引信息)。

其次，B+樹(shù)葉子節(jié)點(diǎn)是鏈接的，所以如果你需要做索引掃描，你可以簡(jiǎn)單的線性遍歷，而不是向上和向下遍歷整個(gè)樹(shù)，從磁盤(pán)上加載更多的索引數(shù)據(jù)。

?

在關(guān)系型數(shù)據(jù)庫(kù)中，B+樹(shù)的結(jié)構(gòu)如下圖：

數(shù)據(jù)庫(kù)中的B+樹(shù)

什么是事務(wù)

事務(wù)是數(shù)據(jù)庫(kù)操作的基本單位，它要么完全成功要么完全失敗，不可能存在部分成功部分失敗的情況。

數(shù)據(jù)不一致

在不同數(shù)據(jù)隔離級(jí)別中可能會(huì)出現(xiàn)一些數(shù)據(jù)不一致現(xiàn)象，了解這些現(xiàn)象對(duì)于調(diào)試你的系統(tǒng)以及了解你的系統(tǒng)能夠容忍什么樣的不一致是至關(guān)重要的。

不可重復(fù)讀(Non-repeatable reads)

不可重復(fù)讀

如上圖所示，如果你在事務(wù)中的兩次后續(xù)讀取之間不能獲得一致的數(shù)據(jù)視圖，就會(huì)發(fā)生不可重復(fù)的讀取。在特定的模式下，數(shù)據(jù)庫(kù)的并發(fā)操作可能會(huì)出現(xiàn)你剛讀的值被修改，導(dǎo)致不可重復(fù)的讀取。

臟讀(Dirty reads)

臟讀

類(lèi)似地，當(dāng)你執(zhí)行了一次讀取，另一個(gè)事務(wù)更新了同一行，但沒(méi)有提交工作，你執(zhí)行了另一次讀取，你可以訪問(wèn)未提交的（臟）值(這不是一個(gè)持久的狀態(tài)變化，與數(shù)據(jù)庫(kù)的狀態(tài)不一致), 就會(huì)發(fā)生臟讀取。

幻讀(Phantom reads)

幻讀

幻象讀取是另一種已提交的數(shù)據(jù)不一致現(xiàn)象，他常發(fā)生在處理數(shù)據(jù)統(tǒng)計(jì)的場(chǎng)景。例如，你在一個(gè)特定的事務(wù)中兩次計(jì)算客戶的總數(shù)。在兩次連續(xù)的讀取之間，另一個(gè)客戶注冊(cè)或刪除了他們的賬戶（已提交），如果你的數(shù)據(jù)庫(kù)不支持這些事務(wù)的范圍鎖，這將導(dǎo)致你得到兩個(gè)不同的值。

隔離級(jí)別

SQL標(biāo)準(zhǔn)的四種隔離級(jí)別

SQL標(biāo)準(zhǔn)定義了4個(gè)標(biāo)準(zhǔn)隔離級(jí)別，這些級(jí)別可以而且應(yīng)該被全局配置（如果我們不能可靠地知道隔離級(jí)別，就會(huì)發(fā)生一些奇怪的問(wèn)題）。

可重復(fù)讀(REPEATABLE READ)

在這個(gè)隔離級(jí)別下，確保在一個(gè)事務(wù)中多次讀取同一數(shù)據(jù)時(shí)，得到的結(jié)果是一致的。

這意味著事務(wù)在開(kāi)始時(shí)會(huì)創(chuàng)建一個(gè)一致的快照，然后在事務(wù)結(jié)束之前，其他事務(wù)對(duì)數(shù)據(jù)的修改不會(huì)影響該事務(wù)的讀取結(jié)果。

在可重復(fù)讀級(jí)別下，解決了不可重復(fù)讀的問(wèn)題，但可能出現(xiàn)幻讀問(wèn)題。

串行化(SERIALIZABLE)

這是最高的隔離級(jí)別，它確保事務(wù)之間的并發(fā)執(zhí)行就像是順序執(zhí)行一樣。

在這個(gè)級(jí)別下，事務(wù)串行執(zhí)行，避免了臟讀、不可重復(fù)讀和幻讀的問(wèn)題。

雖然序列化提供了最高的數(shù)據(jù)一致性，但也犧牲了并發(fā)性能，因?yàn)槭聞?wù)必須依次執(zhí)行，不能并行處理。

讀提交(READ COMMITTED)

在這個(gè)隔離級(jí)別下，一個(gè)事務(wù)只能讀取到已經(jīng)提交的數(shù)據(jù)。這意味著臟讀的問(wèn)題被解決了，因?yàn)槭聞?wù)只能看到其他事務(wù)已經(jīng)提交的數(shù)據(jù)。

然而，在這個(gè)級(jí)別下，可能會(huì)出現(xiàn)不可重復(fù)讀問(wèn)題。

讀未提交

在這個(gè)隔離級(jí)別下，一個(gè)事務(wù)可以讀取到另一個(gè)事務(wù)尚未提交的數(shù)據(jù)。這意味著一個(gè)事務(wù)可能會(huì)讀取到臟數(shù)據(jù)（未經(jīng)提交的數(shù)據(jù)），即臟讀。

這個(gè)級(jí)別提供了最低的隔離性，允許并發(fā)事務(wù)之間產(chǎn)生相互干擾。