- 課程目標

- 表索引

????? ??

? ? 做一定范圍掃描的查詢需要用到表索引，在這種情況下，hash 表并不能滿足要求，因為 hash 表只能用來進行單個 key 的查找

? ??

? ??

? ? 那么表索引是什么？

? ??

? ? 簡單來講，表索引就是 表中屬性 的 子集 的一個 副本，它以一種更高效的方式存儲，以方便能做更高效的查詢操作（相比循序掃描來說）

? ??

? ? 注意，表索引是該表的一個副本，它必須和表保持同步。比如如果表中的某個 tuple 有更新，那么這個更新也應該反映到對應的索引上

? ??

? ? 表索引的操作對于應用開發(fā)人員來講，是完全透明的

? ??

? ??

? ? 雖然大量的索引可以讓查詢變得更快，但維護這個表索引也需要一定的代價，所以就存在 trade-off。比如大量的索引會占用 page 和 Buffer 池的空間，將它寫出到磁盤時，就會占用磁盤空間。如果表里面有 1000 條索引，現(xiàn)在要進行插入操作，那么就必須對這些索引更新 1000 次，直到這些索引被修改完成，這個插入操作才會被認為已經(jīng)完成了。

? ??

? ? 在做查詢操作時，DBMS 自己會去選擇對于查詢來講最優(yōu)的索引，即查詢優(yōu)化

? ??

- B+ Tree? ??

? ??

? ? 有一類數(shù)據(jù)結構叫做 B-Trees（B 樹家族），在它里面，有一種特定的數(shù)據(jù)結構，叫做 B-Tree。

? ??

? ? 實際上 B-Tree 和 B+ Tree 是不同的數(shù)據(jù)結構

? ??

? ? B-Tree 是在 1971 年提出的，2 年后的 1973 年提出的 B+ Tree，那個時候并沒有什么 paper 去描述什么是 B+ Tree，不過 1979 年倒是有篇 paper 做了對 B+ Tree 和 B-Tree 的描述

? ??

? ? 順便，IBM 在 1973 年發(fā)明了 B+ Tree

? ??

? ? 然后在 70-80 年代間，出現(xiàn)了它們的很多變種，比如 B* Tree 是 B-Tree 的變種，而 B^link - Tree 是在 1981 年出現(xiàn)的，由 CMU 首發(fā)

? ??

? ??

? ? 即 《Efficent Locking for Concurrent Operations on B-Trees》，作者 Philip Lehman，現(xiàn)在依然在 CMU

? ??

? ? 數(shù)據(jù)庫系統(tǒng)一般用的是 B+ Tree 而不是 B-Tree，雖然 PostgreSQL 文檔中寫的是用 B-Tree，但實際上它用的就是 B+ Tree

? ??

? ??

? ? B+ Tree 是一種自平衡的樹形數(shù)據(jù)結構，B means Balance

? ??

? ? 基本思想是，往 B+ Tree 中插入數(shù)據(jù)時，它會保證數(shù)據(jù)的有序性，這允許我們可以沿著葉子節(jié)點進行高效的搜索或者循序掃描，插入和刪除的時間復雜度都是 O(log n)，因為 B+ Tree 是平衡的，所以它的復雜度始終是 O(log n)，即對于一個葉子節(jié)點上的任何 key 來說，不管它距離根節(jié)點有多遠，時間復雜度始終是 O(log n)

? ??

? ? B+ Tree 是這樣一種數(shù)據(jù)結構，它能在磁盤非常緩慢，并且內(nèi)存有限的情況下，進行高效地索引查找

? ??

? ? 相比于 B-Tree，B+ Tree 有一個很棒的優(yōu)勢，就是當遍歷到 B+ Tree 底部時，可以沿著葉子節(jié)點進行循序掃描，無須回過頭再遞歸遍歷。因為從上到下，按范圍找到了樹的父節(jié)點下指代的某段區(qū)域葉子節(jié)點，結果就在這個范圍內(nèi)，循序掃描就好了

? ??

? ? 一篇被很多人引用的 paper -- 《The Ubiquitous B-Tree》

? ??

? ? 那么 B+ Tree 有哪些屬性呢？

? ??

? ??

? ? B+ Tree 被認為是一種多路查找樹（Multi-way search tree），意味著在樹中的每個節(jié)點處，它可以通過 M 條（也不完全總是 M 條）不同的路線到達其他節(jié)點

? ??

? ? 注意，這里的 平衡 指的是，任何葉子節(jié)點到根節(jié)點始終是 O(log n)

? ??

? ? 這里，每個節(jié)點必須保證至少是半滿的，對于能存放自節(jié)點中 key 的數(shù)量來說，B+ Tree 中節(jié)點所管理的 key 的數(shù)量至少為 M/2 - 1 個（這里的 M 指樹的高度），但 key 的數(shù)量必須小于 M - 1。刪除的時候，如果節(jié)點不處于半滿的狀態(tài)，那么就得將周圍得數(shù)據(jù)移到這個節(jié)點中，讓它變成半滿的狀態(tài)

? ??

? ? 如果一個 inner node 中有 k 個 key，那么對于這個 inner node 來講就有 k + 1 個非空 children 節(jié)點

? ??

? ? 例子

? ??

? ??

? ? 在任何 inner node 中，它們并沒有 sibling pointer，但葉子節(jié)點有

? ??

? ??

? ? inner node 是 key 和 指針 的結合體，inner node 里面的指針始終指向的是另一個節(jié)點，如果什么也沒有就指向 null，key 就是在任意屬性上構建的索引。當使用一個給定的 key 來進行搜索時，可以通過比對這些 inner node 中 key 的大小來決定該往哪邊遍歷

? ??

? ??

? ? 對于葉子節(jié)點，它有 key 也有 value，這個 value 可以是一個 tuple 的 record ID，也可以是 tuple 自身

? ??

? ? inner node 主要保存的是指針，而葉子節(jié)點主要保存的是數(shù)據(jù)

? ??

? ??

? ? 每個 B+ Tree 的節(jié)點其實就是一個 key/value 對 數(shù)組。如果你是在葉子節(jié)點上，那么可以通過 key 來判斷這是不是你要的東西；如果是在 inner node 上，那么可以通過 key 來判斷你是往左走還是往右走

? ??

? ? 例子? ??

? ??

? ??

? ? 圖中可以看出，B+ Tree 中葉子節(jié)點里，key/value 對是分開存儲的，但這里的 key/value 始終都在同一個 page 上，分開存的原因是它們的大小不一樣

? ??

? ? 使用二分查找并不需要用到 value，只需要用到的是 key，分開來可以更高效地在 key 之間跳轉，而 value 通常情況下是固定長度的，可能是 32/64 bit 長度的 record ID。

? ??

? ??

? ? 它的工作方式是，無論 key 數(shù)組中的 offset 值是什么，它始終對應了 value 數(shù)組中的某些 offset 值

? ??

? ??

? ? 葉子節(jié)點通常有 2 種值

? ??

? ? 1. record ID

? ? 2. Tuple 數(shù)據(jù)

? ??

? ? Tuple 數(shù)據(jù)實際上是存放在葉子節(jié)點上的，第二索引把 record ID 作為值存起來

? ??

? ? MySQL 和 SQLite 大概就是方案 2 存法，而 Oracle 和 SQL Server 默認情況下使用的是方案 1（也就是說它們也可以選擇方案 2）

? ??

- B-Tree vs. B+ Tree

? ??

? ? 在 B-Tree 中，value 可以存放在樹的任何位置，即任何 inner node 可以保存 record ID 或者 tuple 之類的 value

? ??

? ? 而在 B+ Tree 中，value 只能放在葉子節(jié)點中

? ??

? ? 那這意味著什么呢？

? ??

? ? 1. 在 B-Tree 中，不會有任何重復的 key

? ? 2. 在 B+ Tree 中，在 inner node 中會存放所有的路標，也就是說會有重復的 key。此外如果刪除了 B+ Tree 上的一個 key，也是基本上是從葉子節(jié)點上移除，并且把這個 key 保存在 inner node 中。因為如果要查找其他的 key，還可以通過這條路線往下查找

? ??

? ? 相比之下，B-Tree 更加經(jīng)濟，占用的空間也少。但當使用多個線程來進行更新操作時，代價會更加昂貴。比如修改/刪除某個 inner node 里面相關指針的指向，在并發(fā)操作下是需要保護的

? ??

? ? 在 B+ Tree 中，只會對葉子節(jié)點進行修改，可能需要將修改結果向上傳播，那么只需要一個方向上的指針就可以做到

? ??

- B+ Tree 插入

? ??

? ? 插入就是先從 inner node 上根據(jù)二分查找對應的 key，小的走左邊大的走右邊，然后找到葉子節(jié)點中有空間的位置進行插入。如果這個葉子節(jié)點沒空間了，那么就必須拆分這個葉子節(jié)點

? ??

? ? 怎么拆分呢？

? ??

? ? 找到葉子節(jié)點的中間位置，將中間位置左邊的所有 key 放入一個節(jié)點，中間位置右邊所有的 key 放入另一個節(jié)點，然后更新父節(jié)點，讓它包含中間這個 key。接著讓一個額外指針來指向剛剛添加的新節(jié)點

? ??

? ? 對于一次插入來說，可能就需要重新整理下整個樹了

? ??

? ? 一個 B+ Tree 的可視化 demo

? ??

? ? [https://cmudb.io/btree](https://cmudb.io/btree)

? ??

? ? 注意這里 degree 的意思是，從節(jié)點處最多能出來幾條路線，比如 degree = 3，對于 inner node 來講，最多只能保存 2 個 key

? ??

? ? 插入是一個遞歸的過程，隨著插入更多的元素，會繼續(xù)對節(jié)點進行拆分，并將這些變化向上傳遞

? ??

? ? 如果有重復的 key 怎么辦？

? ??

? ??

? ? 那么就會是如上圖那樣的結構，在真實的系統(tǒng)中，重復的 key 可以存在，只需要維護擁有同一個 key 下多個 entry 所對應的值，即每個 entry 對應一個唯一值即可

? ??

- B+ Tree 刪除

? ??

? ? 刪除操作會導致節(jié)點上保存的 key 的數(shù)量小于半滿的情況，這就會違反在 B+ Tree 中必須遵守的原則，因此就得做拆分的逆向操作，也就是 合并

? ??

? ? 一個簡單技巧就是看下臨近的其他葉子節(jié)點中的元素，并嘗試從它們中搶一個 key 過來，以此讓樹變得平衡

? ??

? ? 只要兄弟節(jié)點和這個要搶別人 key 的節(jié)點有相同的父節(jié)點，那么就可以去搶，因為這就不需要對上面那些節(jié)點做任何重新平衡的操作了

? ??

? ? 合并的工作方式是，向下遍歷，會維護一個 stack，里面包含了它向下遍歷元素的記錄。實際上在向下遍歷時，會進行 latch crabbing 或者是 coupling 之類的事情。

- B+ Tree in Practice

? ??

? ? 通常情況下，使用 B+ Tree 保存的數(shù)據(jù)，實際上只有大概 67% 是有用的，其他的都是初始數(shù)據(jù)或者未知數(shù)據(jù)

? ??

- 聚簇索引（Clustered Indexes）

? ??

? ? 一張表的數(shù)據(jù)堆在一起，就是 table heap，而 table heap 是無序的

? ??

? ? 當創(chuàng)建一張表時，可以定義一個索引，數(shù)據(jù)庫系統(tǒng)會保證索引會對 page 中 tuple 的物理布局進行匹配排序，即對磁盤上實際數(shù)據(jù)重新組織以按指定的一個或多個列的值排序

? ??

? ? 這對于一些任務是有利的，比如一大堆根據(jù)主鍵來進行范圍查找的任務，在這些任務中，如果知道 tuple 保存的順序是跟主鍵一致的，那就只需要遍歷某個葉子節(jié)點下所包含的一小部分 page，就可以找到要查找的數(shù)據(jù)。如果不一致，那么拿到的每個 record ID （表中每條數(shù)據(jù)）都有可能指向另一個 page，在讀數(shù)據(jù)時就要進行大量的隨機 I/O

? ??

? ? 注意，聚簇索引也會將 tuple 保存在索引中

? ??

? ? 在 MySQL 中，如果沒有定義主鍵，那它會幫你定義一個，會使用 row ID 或者 record ID 之類的東西作為主鍵，對于調(diào)用 MySQL 的應用開發(fā)者來說，它們是透明的

? ??

? ? 在 PostgreSQL 中，在對表使用聚簇索引時，它并不會按照這個索引的順序來維護，即磁盤上保存的表的數(shù)據(jù)一開始是排好序的，但隨著時間的推移，它就會亂序

? ??

- 在 B+ Tree 上查找

? ??

? ? 如果一個查詢條件包括 a、b、c 3 個，B+ Tree 支持除了 c 之外即只有 a 和 b 兩個的查詢，同時也支持只有 b 一個的查詢，但這是 hash 索引做不到的，因為在不使用 c 的情況下，hash 索引對 a 和 b 進行 hash 后的位置會跳轉到某個隨機的位置上

? ??

? ? 不是所有數(shù)據(jù)庫系統(tǒng)都支持這種查找，但有許多是支持前綴查找（即只查 a 和 b），所有的系統(tǒng)都支持中間的這個 b 類似的查找

? ??

? ? 例子

? ??

? ? 假設在 2 個列或者 2 個屬性上定義一個索引，即復合鍵（composite key），注意這并不是在 1 列上定義索引，而是使用 2 列來進行索引定義

? ??

? ??

? ? 比如要找 （A，B） 這樣的查詢

? ??

? ??

? ? 用條件進行比對和二分查找，就能找到那個對應的 entry

? ??

? ? 但是如果要找 （A，*）這樣的前綴查詢

? ??

? ??

? ? 在找到對應的葉子節(jié)點后，需要對葉子節(jié)點進行循序掃描，直到找到第一個元素 > A 的情況才停止查找

? ??

? ? 比較難實現(xiàn)的是找 （*，B）這樣的后綴查詢

? ??

? ? 需要嘗試在根節(jié)點處弄清楚需要去查看這個樹的哪一部分，然后通過替換 * 來進行查找

? ??

? ??

? ? > 注意上圖中這里 C 中的列表也需要遍歷

? ??

? ? Oracle 把這種查找叫做 skip scan

? ??

? ? 一本 Goetz Graefe 寫的關于 B+ Tree 的參考書? ??

? ??

? ??

? ? 這本書寫的所有關于 B+ Tree 的現(xiàn)代技術和優(yōu)化方法，都可以在真實的系統(tǒng)或者是 B+ Tree 中進行使用

? ??

- Node Size

? ??

? ? 一般來講，可以將 B+ Tree 中的一個 node 當作是表中的 page 來看待，一個 node 的大小可能等于一個 page 的大小

? ??

? ? 如果使用的磁盤速度很慢，那么當構建樹上的索引時，會希望這個節(jié)點 size 更大一點

? ??

? ? 但如果跳到不同節(jié)點間隨機 I/O 的速度非常快，那么節(jié)點就可以使用更小的 size

? ??

? ? 注意尋址速度 內(nèi)存 > SSD > HDD，尋址不需要加鎖，但讀寫需要

? ??

? ? 對于葉子節(jié)點上的掃描來講，由于用的是耗時長的循序掃描，那么這種就更適合 size 更大的節(jié)點

? ??

- 合并臨界點

? ??

? ? 當節(jié)點沒有達到半滿狀態(tài)的情況下，可能實際上不需要立即進行合并操作，因為可能下次操作是插入數(shù)據(jù)，之前做了合并現(xiàn)在又拆開來，那么就會有代價

? ??

? ? 然而合并操作的代價是高昂的，拆分的代價也同樣昂貴

? ??

? ? 隨著時間的推移，樹可能變得不平衡，但可以在后臺使用類似 GC 的東西來對它做重新平衡的操作，或者直接重建這個樹

? ??

? ? 比如很多高端商用企業(yè)級數(shù)據(jù)庫，周末時關閉數(shù)據(jù)庫，重建它們所有的索引，簡單來講這就是它們重新平衡這個樹的方式（草）

? ??

- 可變長度 key

? ? 在節(jié)點中保存可變長度的 key 是一個問題，下面是它的相對應的解決方法

? ??

? ? 1. 雖然保存指針的方式會使得保存的數(shù)據(jù)量變少，但是訪問會很慢，在內(nèi)存很貴的 1980 年代，人們嘗試在內(nèi)存型數(shù)據(jù)庫中使用這個方法，但現(xiàn)在沒人用了

? ? 2. 使用可變長度的節(jié)點的意思是，允許一個節(jié)點的大小根據(jù)它保存的東西來變化，這是一個 bad idea，因為在 Buffer 池和磁盤中 page 的大小應該始終保持一致，這樣才無須擔心該如何找到空閑的空間把數(shù)據(jù)放進去，同樣現(xiàn)在也沒人用這個方法了

? ? 3. 使用填充（padding），不管是什么 key，都使用 null 或者 0 對其填充，以此來適合節(jié)點大小。雖然有一些數(shù)據(jù)庫系統(tǒng)采用了這個方法，然而這存在 trade-off，雖然數(shù)據(jù)能保存，但空間被浪費掉了，這也是為什么說確保 schema 的正確定義是非常重要的。

? ? 4. 更為常見的方法是使用一個間接映射，把 key 指針放在 key 數(shù)組中，注意，這里的指針指的是 2 個在該節(jié)點中對應的 offset 值，而不是指向其他任何 page，它看起來應該像下圖

? ??

? ? ? ??

? ? ? ? 注意這里的 key map 是有序的

? ? ? ??

? ? ? ? 布局和 slotted page 中的 tuple 很像

? ? ? ??

? ? ? ? 這里的 key + value 是從后往前存儲，而 sorted key map 則是從前往后存儲

? ? ? ??

? ? ? ? 如果這個節(jié)點沒有足夠的空間來存數(shù)據(jù)，那么可以使用一個 overflow page 接著存

? ? ? ??

? ? ? ? 那么如何優(yōu)化才能讓這個查找變得更快呢？

? ? ? ??

? ? ? ? 通常來講，sorted key map 數(shù)組中只有 16bit 大小的空間，所以一個可能性的優(yōu)化是，將每個字符串的首字母放在 sorted key map 中

? ? ? ??

? ? ? ??

? ? ? ? 在查找時，如果 key 無法和這里的第一個字符準確匹配，那么也沒有遍歷下去的必要了

? ? ? ??

? ? ? ? 注意，這個優(yōu)化都是在內(nèi)存中做的，因為可以避免 cache miss，同時讓二分查找或其他查找變得更快

? ? ? ??

- 非唯一索引? ??

? ??

? ? 1. 可以復制 key，復制的 key 會被拆分到另一個節(jié)點中，但必須要小心這種情況，而且也要確保讀取了所需要的一切數(shù)據(jù)

? ??

? ? ? ??

? ? ? ? 比如上圖中有重復的 K1，如果要再插入一個 K1，就把 sorted key 中其他元素重新移動排序，那么就依然還能工作，因為里面存放的 offset 值沒有發(fā)生改變

? ? ? ??

? ? 2. 用一個 value 列表，只保存 key 一次，然后在節(jié)點中使用一個單獨的區(qū)域來保存給定 key 的所有 value

? ??

? ? ? ??

? ? ? ? 比如 K1 有其中一個對應的 value 列表，sorted key 中 K1 通過一個指針指向了該節(jié)點里某個 offset 處

? ? ? ??

? ??

? ? 第 1 種方法更常用? ??

? ??

- 節(jié)點內(nèi)的搜索方式

? ??

? ? interpolation 的意思是指，如果知道要查找的 key 的大概的大小，同時也知道這些 key 的分布信息，就可以用簡單的數(shù)學方法來進行處理（這里是不是存儲的時候就要符合某些數(shù)學規(guī)律？）

? ??

? ??

? ? 比如，數(shù)組中存有 7 個 key，而 key 的值最大為 10，如果要找的是 8，那么就可以用上面的公式，因為這個數(shù)據(jù)的存儲規(guī)律是單調(diào)遞增的，所以可以這么算

? ??

? ? 但是這種情況，不適用于浮點數(shù)和字符串的查找

? ??

- 優(yōu)化

? ??

? ? 1. 壓縮數(shù)據(jù)

? ??

? ? ? ??

? ? ? ? 前綴壓縮（prefix compression），它是基于 key 都是有序排列的

? ? ? ??

? ? ? ? 在很多數(shù)據(jù)集中，很有可能會出現(xiàn)保存在同一節(jié)點上的 key 彼此之間會非常相似，因為被排過序了

? ? ? ??

? ? ? ? 比如例子中的 robbed/robing/robot，它們都有共同的前綴 rob，所以對于每一個 key 而言，沒必要反復復制或存儲這個冗余字符串 rob，而是將它提取出來

? ? ? ??

? ? ? ??

? ? ? ? 這也被成為 Prefix Tree（也就是 Trie Tree）

? ??

? ? ? ? Meta 在它內(nèi)部的 MySQL 中都做了這個優(yōu)化，這引起了性能上的巨大差異，因為這樣做節(jié)省了大量的空間，在數(shù)據(jù)庫中，重復的數(shù)據(jù)實在是太多了

? ??

? ? ? ? 另一種類似的優(yōu)化是在聚簇索引中，我們知道所有的 tuple 都放在磁盤或者 page 中，那么同樣在索引中，它們是以排序存在的，那么 tuple 有可能在同一個節(jié)點上，它們的 record ID 會使用相同的 page ID，這個時候也沒必要把這種情況下單個 tuple 的 page ID 反復存放在一個節(jié)點中，而是只保存一次 page ID，然后將它們的 offset 值或者 slot 分開存放

? ? 2. 后綴截斷（suffix truncation）

? ??

? ? ? ??

? ? ? ? 基本思路是，無須在 inner node 中存儲完整的 key 值，來判斷向左走還是向右走，而是在 inner node 中存儲能夠區(qū)分 key 的唯一前綴即可，然后將剩余的后綴拋棄掉

? ? ? ??

? ? ? ??

? ? ? ? 注意在下面的節(jié)點中，得依然存儲整個 key

? ? ? ??

? ? ? ? 前綴壓縮遠比后綴截斷常用

? ? ? ??

? ? 3. Bulk Insert

? ? ? ??

? ? ? ? 很多時候，人們會這么做，打開所有索引，批量加載數(shù)據(jù)，并將數(shù)據(jù)插入表中，然后回過頭來添加索引，但當你插入新數(shù)據(jù)時不應該去維護索引，因為這么做代價太高了

? ? ? ??

? ? ? ? 如果提前就有了所有的 key，就可以用一種很簡單的優(yōu)化方式來構建索引，不會像之前那樣自上而下地去構建它，而是自下而上地去做這件事

? ? ? ??

? ? ? ? 怎么做呢？

? ? ? ??

? ? ? ? 對于一組已知的 key 來說，可以對其先排序

? ? ? ??

? ? ? ??

? ? ? ? 然后將它們排列在葉子節(jié)點上，正確地填入到葉子節(jié)點中

? ? ? ??

? ? ? ??

? ? ? ? 然后自下而上，只需要使用中間 key 來填充 inner node，并生成對應的指針

? ? ? ??

? ? ? ??

? ? ? ? 這是任何主流數(shù)據(jù)庫系統(tǒng)都支持的一種標準技術

? ? ? ??

? ? ? ? 使用批量插入（bulk insert）來構建索引，速度會非?？?/p>

? ? ? ??

? ? - Pointer Swizzling

? ??

? ? ? ??

? ? ? ? 實際上，在數(shù)據(jù)庫實現(xiàn)的 B+ Tree 中，節(jié)點保存的指針并不是原始的內(nèi)存指針，而是 page ID

? ? ? ??

? ? ? ??

? ? ? ? 比如查找 key > 3 的數(shù)據(jù)，怎么去找上圖中右下的節(jié)點找數(shù)據(jù)呢？

? ? ? ??

? ? ? ? 在根節(jié)點處，保存了該索引的 page ID

? ? ? ??

? ? ? ??

? ? ? ? 然后需要跑到下面的 Buffer 池中找 page #2，如果它不在內(nèi)存中，Buffer 池應該返回一個指向它的指針

? ? ? ??

? ? ? ??

? ? ? ? 如果拿到了這個指針，就可以對節(jié)點進行遍歷了

? ? ? ??

? ? ? ? 而對于兄弟節(jié)點的遍歷也是一樣的

? ? ? ??

? ? ? ??

? ? ? ? 但這樣做的代價很高，因為必須使用 latch 來保護 Buffer 池中的 hash 表，要花很多步驟才能拿到這個指針

? ? ? ??

? ? ? ? 所以為了解決上述問題，pointer swizzling 的思路是（或者說假設是），如果內(nèi)存中所有的 page 都是固定住的話，那么它們永遠不會移動到另一個內(nèi)存地址上去

? ? ? ??

? ? ? ? 比如下圖中，節(jié)點不會保存 page ID，而是保存 page 指針

? ? ? ??

? ? ? ??

? ? ? ? 這樣就不用訪問 Buffer 池，也會避免上面的一些問題

? ? ? ??

? ? ? ? 當然這樣做也要確保一件事情，那就是，如果要將它從內(nèi)存中移除，也就是將它寫出到磁盤上，那么就不要保存 page 指針，因為當它再放入內(nèi)存時，地址就變了

? ? ? ??

? ? ? ? 所以這里也無須將 page ID 完全不要，可以通過一點額外的元數(shù)據(jù)來表示，這就是我們想要的指針，而不是 page ID

? ? ? ??

? ? ? ? 對于樹的上層部分，比如根節(jié)點或者是樹的第二層處的節(jié)點，它們的使用頻率都非常高，因為都需要經(jīng)過它們才能訪問到下一級的節(jié)點的數(shù)據(jù)，所以將這些上層節(jié)點數(shù)據(jù)對應的 page 固定住可能并沒有什么大問題，比起整個樹的 size 來講，這些上層節(jié)點所占的體積還是比較小的。那么針對這種情況就可以使用這種優(yōu)化策略，因為 page 固定，指針始終有效

? ? ? ??

? ? ? ? 這種方式實際上非常普遍，很多主流數(shù)據(jù)庫系統(tǒng)中都使用了這種方法

? ? ? ??

- 結論

? ??