頁就是節點
索引存放在固定大小、最多容納 2k 個索引元素的頁上，而這些頁正好就是樹的節點。整個關鍵就在這個等同關係：走訪一個節點的代價是一次裝置存取，與節點裡有幾個鍵無關，所以把節點放大到一個傳輸單位，等於用一次尋道換來最多 2k+1 的分支度。以作者選用的 k = 60 為例，高度 3 的樹已經可以索引到 1,771,560 個鍵，也就是說在很大的索引裡查一筆只需要三次讀頁。這個結構是圍繞裝置參數設計的，而不是圍繞抽象的比較次數。
一口氣講完 — 整篇論文的濃縮
Bayer 與 McCreight 處理的問題是：當一個隨機存取檔案持續變動，而它的索引又大到放不進主記憶體、必須擺在磁碟或磁鼓上時，該如何組織與維護這個索引。他們的答案是讓樹的節點單位等於資料傳輸單位：每個節點就是一頁，一頁存放 k 到 2k 個索引元素，因此一個節點有 k+1 到 2k+1 個子節點，整棵樹極為扁平。平衡不是靠旋轉維持，而是靠由下往上生長：一個已滿的頁再收到一筆項目時，就在中位數鍵處分裂，中位數被推上父頁；樹高唯一會增加的時機，是根節點自己分裂而必須產生新根。刪除則是完全對稱的操作，用相鄰兄弟頁的串接（catenation）處理，若兩頁合起來太滿無法合併，就改用下溢（underflow）把鍵重新平均分配。查詢、插入、刪除的頁存取次數都與樹高成正比，而樹高的上界是 1 + log_(k+1)((I+1)/2)；儲存空間利用率保證至少 50%，加上上溢（overflow）最佳化後，隨機插入實測達 86.7%，循序插入則超過 99%。
在這篇論文之前 — 它所降落的世界
在這篇論文之前，作者引用的平衡樹文獻談的都是活在記憶體裡的結構：Adelson-Velskii 與 Landis 的 AVL tree、Foster 用 AVL 做資訊檢索、Landauer 的平衡樹、Sussenguth 用樹結構處理檔案。這些設計計算的是節點走訪次數，對核心記憶體是對的成本模型，對移動磁頭的磁碟卻完全錯誤：一次存取要等約 50 毫秒，但接下來的傳輸每個索引元素只要約 90 微秒。因此在大型索引上，二元結構的一次查詢要付出數十次磁碟尋道，因為每一次指標追蹤都是一次獨立的裝置存取。當時實務上的競爭方案是雜湊（hash-coding），論文也明白點名：它的單點查詢很快，但破壞了鍵的自然順序，而且在儲存佔用率很高時效能會嚴重劣化。真正缺的，是一個在這類準隨機存取裝置上便宜、又保留鍵順序、還能無限期吸收插入與刪除而不需重整的索引。
問題 — 當時真正壞掉的地方
- 索引體積龐大，主記憶體一次只能放進很小一部分，主體必須存放在存取或等待時間很長、但一旦開始傳輸資料率就很高的後備儲存裝置上。
- 由於底層資料檔案本身會變動，索引必須能經濟地插入與刪除索引元素，而不只是查詢，而且要就地完成，不能靠定期重建。
- 像平衡二元樹這種以節點走訪次數計價的結構，會把每一層都變成一次獨立的裝置存取，而那正是要花 50 毫秒、必須極力減少的動作。
- 雜湊式組織放棄了鍵的自然順序，而正是這個順序才使得找前驅與後繼、循序掃描檔案回答查詢、以及一次取出一段連續鍵成為可能。
- 儲存空間必須隨檔案成長與收縮而動態申請與釋放，而且在後備儲存佔用率很高時，不能出現壅塞問題，也不能有效能劣化。
- 所需的界限必須在任何時刻都成立，而不是重建之後的平均值：查詢、插入、刪除三者都要有與索引大小的對數成正比的保證成本。
核心概念 — 主要貢獻，以及它們為何成立
B-tree 類別 T(k,h)
屬於 T(k,h) 的 B-tree 是一棵有向樹：從根到任一葉的每條路徑長度都等於 h；除了根與葉以外的每個節點至少有 k+1 個子節點；根本身是葉，或至少有兩個子節點；任何節點的子節點數都不超過 2k+1。索引在此之上再加上兩條規定：除根頁可放 1 到 2k 個鍵外，每頁存放 k 到 2k 個鍵；有 l 個鍵的非葉頁恰好有 l+1 個子節點。所有葉子同深度這條不變量，讓每次查詢的成本完全一致；每頁至少 k 個鍵這條下界，則同時保證了對數樹高與至少 50% 的空間利用率。這個類別是用不等式而非固定形狀定義的，正因如此，它才能吸收任意的更新序列而永遠不會失衡。
由葉往根生長
平衡的維持完全不需要旋轉，也不需要額外的再平衡走訪。分裂與串接只從葉節點發起，然後往根的方向傳播；如果根節點分裂，就必須產生一個新的根，而這是樹高唯一可能增加的方式。因為分裂是在頂端加一層，而不是把某一條分支拉長，所有從根到葉的路徑會在同一瞬間一起加一，同高度的不變量因此自動維持。收縮時同樣的論證反過來跑，於是整棵樹是繞著根呼吸，而不是被重新整理。
在中位數鍵處分裂
當一筆項目要插入一個已經有 2k 個鍵的頁時，先在主記憶體裡邏輯上插入，得到 2k+1 筆項目的序列，前 k 筆留在原頁 P，後 k 筆搬到全新的兄弟頁 P'，中位數項目 x_(k+1) 連同指向 P' 的指標則插入父頁 Q。選在中位數切開，正是為了保證兩半各自恰好有 k 個鍵，所以分裂永遠不會破壞「每頁至少 k 個鍵」的下界。插入 Q 當然可能導致 Q 也分裂，如此沿路徑往上，但每一層最多只被動到一次。作者特別指出，這個過程把參數為 k 的 B-tree 映到參數同樣為 k 的 B-tree，並且保持鍵的排序條件不變。
刪除靠串接與下溢
刪除位於葉頁上的鍵可以直接進行；刪除位於中間頁的鍵，則必須用它右側子樹中最小的鍵取代，做法是從該子樹的根沿著 p_0 指標一路走到葉頁，取該葉頁的第一個鍵，再把這個鍵從葉頁刪掉。這時葉頁可能只剩不到 k 個鍵，修補方式靠數鍵決定：若該葉頁與相鄰兄弟頁合起來不超過 2k 個鍵，兩頁串接成一頁，父頁中的分隔鍵被拉下來，父頁因此可能也不足 k 個鍵，於是往上傳播。若兩頁合起來超過 2k 個鍵，就在主記憶體中先合併再從中間切開，作者稱為下溢；作者並指出下溢不會往上傳播，因為父頁只是被修改，鍵數並沒有改變。刪除因此是插入的精確逆操作，具有相同的區域性與相同的終止論證。
先上溢，再分裂
在基本方案中，由於每頁可能只放 k 個鍵，利用率最差會掉到 50%，所以論文替插入加了一條「再給一次機會」的規則。如果要插入的頁已滿，但相鄰兄弟頁還沒滿，就把鍵先插進序列，再對這兩頁做下溢式的重新分配，於是根本不必分裂；只有在兩側相鄰兄弟頁都滿的時候，一頁才會被分裂。在沒有刪除的索引中，這把最壞情況的空間利用率從 50% 拉高到約 66%，代價是成本界限變差：最壞情況的插入讀頁數從 h 上升到 3h-2。這個想法後來成為 B*-tree，而作者當時就已經指出，可以把候選鄰居的範圍擴大到相鄰兄弟以外，把最低佔用率再往上推。
由裝置參數決定 k
論文沒有把頁大小交給直覺。它把讀寫一頁的時間模型化為 alpha + beta(2k+1) + gamma ln(vk+1)：alpha 是每頁的固定成本，例如平均磁碟尋道時間加上 CPU 額外負擔；beta 是每筆項目的傳輸時間；gamma 涵蓋頁內二分搜尋的對數部分；v 介於 1 與 2 之間，是平均頁佔用率因子。乘上樹高（約為 log_(vk+1)(I+1)）就得到每筆交易的總時間，並可解出最佳 k 的封閉條件式。以 IBM 2311 磁碟實測得到的 alpha = 50 毫秒、beta = 90 微秒代入，Figure 8 的表格顯示 64 到 128 是 k 的可接受範圍；作者基於程式撰寫方便，選了 k = 60，也就是一頁 120 個索引元素。
運作方式 — 具體的機制
頁的版面配置與排序不變量
一個頁 P 以遞增順序存放 x_1 到 x_l，其中 k <= l <= 2k（根頁則是 1 <= l <= 2k），另外還有 l+1 個子節點指標 p_0 到 p_l；在葉頁上這些指標是未定義的。三元組 (x_i, alpha_i, p_i)，或省略關聯資訊後的配對 (x_i, p_i)，稱為一筆項目（entry）。以 K(p_i) 表示以 p_i 所指頁為根的最大子樹中所有鍵的集合，結構在任何時刻都維持三個條件：K(p_0) 中的每個鍵都小於 x_1；對 i 從 1 到 l-1，K(p_i) 中的每個鍵嚴格落在 x_i 與 x_(i+1) 之間；K(p_l) 中的每個鍵都大於 x_l。這三條是所有演算法都必須保持的不變量，也正是它們讓「頁內搜尋一次」就足以選出正確的子節點。
查詢
查詢從指向根的指標 r 開始（樹為空時 r 未定義），然後往下走。在每一頁掃描 P(p) 的鍵尋找目標鍵 y：若 y 等於某個 x_i 則查詢成功，否則排序條件會唯一決定該往哪個子指標下降。論文指出，演算法邏輯上雖然寫成線性掃描，實際實作應該在頁內採用二分搜尋這類有效率的技巧，因為一頁最多有 2k 個鍵。有一個副作用對下一個演算法很重要：變數 s 會停在最後掃描過的那一頁，讓插入可以直接從葉頁開始，不必再走一次。整個過程最多掃描並讀取 h 頁，所以 f_min = 1、f_max = h，而且完全不寫頁。
插入
要插入鍵 y，先執行查詢演算法。若找到 y，表示索引中已有此鍵。若 s 未定義，表示樹是空的，建立一個含 y 的根頁。否則，若葉頁 P(s) 未滿，直接把項目 (y, u) 插入該頁並寫回一頁。若 P(s) 已滿，就執行分裂程序：中位數被推上父頁，分裂可能沿著查詢路徑往上串連，最後甚至產生新的根頁。由於查詢路徑上有 h 頁，最壞情況要寫 2h+1 頁（h 頁各裂成兩頁，再加一個新根），但讀取仍然只有 h 頁，因此 f_max = h、w_max = 2h+1，其中 h 一律指舊樹的高度。
刪除
先用查詢演算法定位 y。若 y 在葉頁上，直接在該頁刪除。若不在，就沿 p_0 指標把沿路各頁讀到葉頁，用該葉頁的第一個鍵取代 y，再把那個第一個鍵從葉頁刪除，如此所有情況都被化約成葉頁刪除。接著，若葉頁的鍵數已少於 k，當它與相鄰兄弟頁合起來不超過 2k 個鍵時執行串接，超過 2k 時則執行下溢。串接會從父頁移走一筆項目，因此可能一路往上串連到根；下溢則只修改父頁而不改變其鍵數，所以立刻停止。最佳情況為 f = h、w = 1；若 y 不在葉頁且沒有任何重整，則 f = h、w = 2；最壞情況是查詢路徑上除了前兩頁以外全部串接、根的兒子發生下溢、根也被修改，此時 f = 2h-1、w = h+1。
成本模型與分頁區
分析假設：單次操作中內容被檢視或修改的任何一頁，都恰好被讀入一次、也恰好被寫出一次；論文並指出主記憶體中只要有能容納 h+1 頁的分頁區，就足以做到這件事。成本因此以 f（讀入頁數）與 w（寫出頁數）來計算，並對每種操作導出最小與最大值。作者刻意不去分析更強的分頁策略，例如把根頁永久鎖在主記憶體裡，儘管他們在實驗中確實用了這類策略，所以論文公布的界限是保守的。對純插入過程而言，建立含 I 個鍵的索引所發生的分裂次數上界是 n(I)-1，其中 n(I) <= I/k + 1，而每次分裂最多多寫兩頁，於是平均每次插入為 f_a = h 次讀取、少於 1 + 2/k 次寫入。
實驗環境
這些演算法被實際寫成程式，並在配備 2311 磁碟機作為後備儲存的 IBM 360/44 上量測；索引元素長 14 個 8 位元字元，索引大小一般約一萬個元素。實作中加入了一個簡單的需求分頁機制，使用約 1250 個索引元素份量的核心記憶體，因此區分了虛擬磁碟讀取（向分頁機制要求某頁必須在核心中）與實體磁碟讀取（只有在分頁區中沒有該頁副本時才會發生）。論文寫作時已完成十組實驗，每組由三件事指定：插入時是否允許上溢、每頁的索引元素數、以及對一個初始為空的索引所施加的交易序列；每組實驗再分成數個階段，每階段結束時記錄效能變數。所報告的量測指標包括儲存利用率百分比、每筆交易的平均虛擬與實體磁碟讀取次數、每次插入或刪除的平均虛擬與實體磁碟寫入次數，以及每秒平均交易數。
論文證明了什麼 — 量測數據與證明
- 含 I 個鍵的頁樹高度有雙向界限：對 I >= 1，h 至少是 log_(2k+1)(I+1)，至多是 1 + log_(k+1)((I+1)/2)，空索引時 h = 0；論文稱這組界限是緊的，因此查詢成本的對數性質是由結構本身保證，而非靠假設。
- 以選定的 k = 60（每頁 120 筆項目）為例，Figure 9 列出各高度所能涵蓋的索引大小：高度 1 為 1 到 120 個鍵，高度 2 為 121 到 14,640，高度 3 為 7,441 到 1,771,560，高度 4 為 453,961 到 214,358,880；也就是說百萬級索引只有三到四次讀頁的深度。
- 更新成本逐項有界：插入最少 f_min = h 次讀取、w_min = 1 次寫入，最壞為 f_max = h、w_max = 2h+1；刪除最好是 f = h、w = 1，最壞為 f_max = 2h-1、w_max = h+1；純插入過程的平均是 f_a = h、w_a < 1 + 2/k，純刪除過程則是 f_a < h + 1 + 1/k、w_a < 4 + 2/k。
- 混合工作負載確實比較差：在 Figure 2 與 Figure 5 的兩棵樹之間交替刪除與插入鍵 9，會讓每一次操作都落在最大成本上；即便如此，論文仍證明這種交互干擾相對於純插入或純刪除，至多讓效能劣化 3 倍。
- 上溢最佳化是實測而非只靠推論：每頁 120 個元素、5,000 次均勻隨機插入的條件下，不允許上溢的儲存利用率為 67.1%（E5），允許上溢則為 86.7%（E6）；依鍵值循序插入 10,000 個元素達到 99.2%（E2），循序插入 100,000 個元素達到 99.8%（E10），在後續的隨機插入、刪除與查詢之後穩定在 82.1%。
- 在配備 2311 磁碟（平均存取延遲約 50 毫秒、每個索引元素傳輸約 90 微秒）的 IBM 360/44 上的端到端吞吐量：15,000 個鍵的索引維持在平均每秒 9 次查詢、插入與刪除，100,000 個鍵的索引則至少每秒 4 次；理論分析並推估 1,500,000 個鍵的索引仍可達到每秒至少 2 筆交易。
限制與取捨 — 論文自承的，以及後來被發現的
- 論文自己承認：插入與刪除的最壞情況界限雖然是緊的，但上下界相距很遠，而且除了病態例子外極少被觸及，因此不是實際成本的好指標。作者退而分析平均成本，但只能在「純插入過程」或「純刪除過程」這種人為假設下進行。
- 論文自己承認：一旦插入與刪除混合，上述平均值就不再成立，交替操作鍵 9 的例子正是反證；作者直言，這種交互干擾在實際應用中有多重要、他們的最壞情況分析有多切題，仍是開放問題。
- 論文自己承認：上溢只能把最壞情況的儲存利用率提高到約 66%，而且僅限於沒有刪除的索引；一旦有刪除，利用率仍可能低到 50%。上溢同時也讓可導出的成本界限變差，最壞情況插入的讀頁數從 h 升到 3h-2，而且很容易構造出每次插入都引發上溢的例子。
- 完全沒有處理的部分：並行控制與復原機制。演算法假設同一時間只有一筆交易，而一次傳播到根的分裂等於要把其他所有讀取者都擋在外面；B-tree 的並行存取要到後來才被解決，包括 Bayer 與 Schkolnick 的鎖定協定（1977）以及 Lehman 與 Yao 的 B-link tree（1981），後者加上右向連結，讓讀取者能追上剛剛分裂過的頁。
- 後續研究揭露的問題：本設計把關聯資訊同時放在中間頁與葉頁，這會降低分支度，也使得有序掃描必須在層與層之間跳躍。實際被生產系統採用的是 B+-tree 變體：把所有索引元素推到葉層，並把葉頁串成鏈結。再往後，B-tree 在隨機插入下只能維持約一半到三分之二的頁佔用率、而且頁面散落在裝置各處，這個特性催生了以 LSM-tree 為代表的寫入最佳化替代方案。
它後來變成什麼 — 繼承這個想法的系統
B-tree 成為整個產業預設的磁碟索引結構，程度之深，讓 Comer 在 1979 年的綜述論文可以直接取名為 The Ubiquitous B-Tree。IBM 的 VSAM 與 System R，以及其後的 DB2、Oracle、Informix，乃至幾乎每一個 SQL 引擎，都以 B-tree 家族索引作為主要存取方法；PostgreSQL 的 nbtree 實作的是 Lehman 與 Yao 的並行 B-link 變體，MySQL InnoDB 把每張表都存成叢集式 B+-tree，而 SQLite、Berkeley DB 與 LMDB 從頭到尾就是 B-tree 引擎。檔案系統的繼承同樣徹底：NTFS、HFS+、XFS、ext4 的 HTree 目錄、Btrfs 與 ReiserFS 全都以 B-tree 變體建立索引。這篇論文中的兩項改良後來各自獨立成名：上溢規則變成 Knuth 所稱的 B*-tree，而只在葉層存資料並把葉頁串鏈的安排則成為 B+-tree，也就是今天大多數人講「B-tree」時真正指的東西。這裡建立的成本模型，也就是把節點大小對齊裝置的傳輸單位、並以裝置存取次數而非比較次數為量測標準，成了後來所有外部記憶體索引的範本，從 cache-oblivious B-tree 一直到 TokuDB 背後的寫入最佳化 B-epsilon tree。它在現代最主要的對手 LSM-tree（O'Neil 等人，1996）及其後代 LevelDB、RocksDB、Cassandra，最好的理解方式就是刻意反向的取捨：放棄 B-tree 的就地更新與讀取簡潔性，換取循序寫入的吞吐量。
論文原文 — 逐字引用
“Storage utilization is at least 50% but generally much higher. The pages of the index are organized in a special data-structure, so-called B-trees.”
“The splitting and catenation processes are initiated at the leaves only and propagate toward the root. If the root node splits, a new root must be introduced, and this is the only way in which the height of the tree can increase.”
“Thus a page will be split only if both adjacent brothers are full, otherwise an overflow occurs.”
術語 — 依本篇論文的用法
- 索引元素（index element）
- 一組固定大小、實體上相鄰的資料項配對 (x, alpha)：鍵 x 唯一識別索引中的一個元素，關聯資訊 alpha 則通常是指向隨機存取檔案中某筆記錄或某組記錄的指標。論文把 alpha 視為不透明、不再深究。
- 頁（page）
- 最多可容納 2k 個鍵的固定大小區塊，它同時是主記憶體與後備儲存之間的資訊傳輸單位，也是樹的一個節點。頁不必被填滿，但除根頁外每一頁至少要有 k 個鍵。
- 準隨機存取裝置（pseudo random access device）
- 論文設定的後備儲存類別：固定磁頭與移動磁頭磁碟、磁鼓、以及資料格（data cell）。相對於核心記憶體這類真正的隨機存取裝置，它們的存取或等待時間相當長，但一旦開始傳輸實體上連續的資料，資料率相當高。
- B-tree，類別 T(k,h)
- 一棵有向樹，若非空樹（h = 0）就必須滿足三項條件：從根到葉的每條路徑長度都是 h；除根與葉之外的每個節點至少有 k+1 個子節點，而根本身是葉或至少有兩個子節點；任何節點的子節點數都不超過 2k+1。不同參數的類別之間不必然互斥。
- 項目（entry）
- 存放在頁內的三元組 (x_i, alpha_i, p_i)，或省略關聯資訊後的配對 (x_i, p_i)。它把一個鍵與一個子節點指標綁在一起，該子樹恰好收納落在 x_i 與 x_(i+1) 之間的所有鍵。
- 分裂（splitting）
- 當一筆項目必須插入一個已有 2k 個鍵的頁時所執行的操作：把 2k+1 筆項目切開，前 k 筆留在 P，後 k 筆移到新的兄弟頁 P'，中位數項目連同指向 P' 的指標插入父頁。分裂只從葉頁發起，並可能一路往上傳播到根。
- 串接（catenation）
- 把兩個相鄰兄弟頁合併成一頁的操作；相鄰兄弟頁指的是有同一個父頁、且被父頁中相鄰指標指到的兩頁，合併條件是兩頁的鍵數合計不超過 2k。父頁中的分隔鍵會被拉進合併後的頁，因此父頁可能剩下不到 k 個鍵，而使整個過程往根的方向傳播。
- 下溢（underflow）
- 當兩個相鄰兄弟頁的鍵數合計超過 2k、無法串接時所採取的替代做法：先在主記憶體中把兩頁串接成一個過大的頁，再從中間切開，使鍵平均分配。下溢不會往上傳播，因為父頁雖被修改，鍵數並沒有改變。
- 上溢（overflow）
- 下溢在插入時的對應操作：若某個鍵必須插入一個已滿的頁，但它的相鄰兄弟頁尚未滿，就先插入再把兩頁重新分配，而不進行分裂。因此只有在兩側相鄰兄弟頁都滿時，一頁才會被分裂，這使得純插入索引的最壞情況利用率提高到約 66%。
在時間軸上的位置 — 這篇論文在整段故事中的座標
年份1970–1972
里程碑B-tree
解決的問題循序式與雜湊式索引無法在磁碟儲存上有效支援範圍查詢、有序走訪與動態插入。
解決方式B-tree 將鍵值組織成平衡、高扇出（fan-out）的樹節點，讓點查詢與範圍掃描的磁碟尋道次數降到最低。
重要性數十年來成為幾乎所有關聯式資料庫、檔案系統與儲存引擎最主要的磁碟索引結構。
DDIACh. 4: Storage & Retrieval