什么是索引

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

就像書后面的索引頁一樣，它可以幫助你找到正確的一頁。

為什么需要索引

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

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

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

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

索引是如何工作的？

一般而言,索引越多讀取性能越好,但這是以寫性能的降低為代價的,因?yàn)槟阈枰３謱λ饕母?/p>

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

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

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

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

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

加入存儲的數(shù)據(jù)規(guī)模無法全部存放到內(nèi)存，或者需要很長的時間才能將數(shù)據(jù)從磁盤加載到內(nèi)存呢？如下表中，數(shù)據(jù)分散在磁盤中，無法完全加載到內(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表)以及一種可以不需要掃描磁盤直接定位到正在查詢的指定行的手段。

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

RowIDs indexes mapping to table data

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

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

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

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

平衡樹(B-Tree)

B樹 VS B+樹

?「B樹 VS B+樹」

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

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

?

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

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

什么是事務(wù)

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

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

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

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

不可重復(fù)讀

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

臟讀(Dirty reads)

臟讀

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

幻讀(Phantom reads)

幻讀

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

隔離級別

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

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

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

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

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

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

串行化(SERIALIZABLE)

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

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

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

讀提交(READ COMMITTED)

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

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

讀未提交

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

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