1969 年，阿波羅 11 號登月成功，這是人類工程學的偉大勝利，也將電腦的能力展現得淋漓盡致。進入 1970 年代，電腦（尤其是 IBM 的大型主機 Mainframe）迅速成為銀行、航空公司、保險公司不可或缺的商業中樞。電腦不再只是科學家的玩具，它們開始管理金錢、訂單和上百萬人的資料。隨之而來的，是軟體規模的空前膨脹——數十萬、乃至數百萬行的程式碼交織在一起。
然而，一個幽靈開始徘徊在電腦科學領域，這就是著名的「軟體危機」(Software Crisis)。人們發現，軟體專案的開發成本極難預估、時程嚴重落後、且交付的產品充滿了錯誤 (Bug)。1960 年代那些天才程式設計師發明的資料結構（如二元搜尋樹）和演算法，在大型專案中卻顯得脆弱不堪。程式碼如同義大利麵般糾纏不清（被稱為「Spaghetti Code」），一個小小的修改就可能引發連鎖災難。
人們痛苦地意識到：僅僅擁有「聰明」的演算法是不夠的。我們需要一種方法，一種「紀律」，來管理這種爆炸性的「複雜性」(Complexity)。我們需要的，不僅是「演算法」，更是「演算法工程」。於是，1970 和 1980 年代，電腦科學兵分兩路，開始了對「秩序」的追求：一條路是「抽象化」，試圖在邏輯上馴服複雜性；另一條路是「平衡化」，試圖在實作上保證系統的絕對可靠。
一、 1970s：抽象化的革命
1. 「結構化」的呼喚
1970 年代初的程式設計，是一片混沌的荒野。當時的主流語言（如 FORTRAN、COBOL）大量依賴 GOTO 語句，程式的執行流程可以在程式碼中隨意跳轉，使得理解和除錯變得極為困難。資料結構的實作是完全「裸露」的：一個程式設計師可能在程式的 A 處，直接修改了 B 程式設計師所寫的某個「陣列」的內部索引，導致了隱晦的錯誤。這種缺乏「邊界」和「保護」的風格，是軟體危機的直接原因。
在這樣的背景下，兩位歐洲的電腦科學家發起了變革的號角。一位是荷蘭的艾茲赫爾·戴克斯特拉 (Edsger W. Dijkstra)，他在 1968 年發表了著名的論文《GOTO 語句被認為是有害的》(Go To Statement Considered Harmful)，倡導使用 if-then-else、while-loop 等「結構化程式設計」(Structured Programming) 來取代混亂的跳轉，讓程式邏輯變得清晰可循。
另一位則是瑞士的尼克勞斯·維爾特 (Niklaus Wirth)。他深刻地認識到，程式的混亂不僅來自於「流程」，更來自於「資料」。他認為，必須將「資料」和「處理資料的流程」緊密地綁定在一起，才能建立可靠的系統。他基於這個理念設計了一門全新的語言——Pascal (1970)。Pascal 語言不僅強制推行結構化流程，更重要的是，它提供了強大的「型別」系統，讓程式設計師可以「定義」自己的資料結構，這為即將到來的革命鋪平了道路。
2. Wirth 與 Hoare：「抽象資料型態」(ADT) 的誕生
1976 年，Niklaus Wirth 寫下了一句傳世名言，並以此作為他一本著作的標題：《演算法 + 資料結構 = 程式》(Algorithms + Data Structures = Programs)。這句話精確地定義了 1970 年代的思想轉變。但與此同時，另一位英國電腦科學家東尼·霍爾 (C. A. R. Hoare，快速排序的發明者) 則在思考一個更深層的問題：我們該如何「定義」資料結構，才能讓它被安全地「重用」？
Hoare 在 1972 年提出了「抽象資料型態」(Abstract Data Type, ADT) 的關鍵概念。這個概念是電腦科學史上的一次重大飛躍。Hoare 指出，一個資料結構（例如「堆疊」Stack）不應該被看作是「一個陣列和一個頂端索引」，而應該被定義為「一組公開的操作 (Operations) 及其行為」。例如，一個 Stack 只有三個操作：push(item)（推入）、pop()（彈出）、isEmpty()（是否為空）。
這個觀念改變了一切。ADT 就像一個「黑盒子」，它向「外部使用者」提供了一組清晰的「介面」(Interface)，而將其「內部實作」(Implementation) 徹底隱藏起來。使用這個 Stack 的人，不需要 知道（也不應該知道）它內部究竟是用「陣列」還是用「鏈結串列」來實作的。這就是「資訊隱藏」(Information Hiding) 與「封裝」(Encapsulation)。
3. 從「技巧」到「模組」
ADT 的革命性影響是巨大的。在 1960 年代，Stack、Queue、Tree 只是程式設計師的「個人技巧」；而在 1970 年代，它們搖身一變，成為了可被定義、可被封裝、可被安全重用的「型別」或「模組」。這場「抽象化革命」讓軟體得以「工程化」。程式設計師可以像組合樂高積木一樣，把一個個高內聚、低耦合的 ADT 模組搭建起來，建造出複雜但依然「可維護」的系統。
這個思想直接催生了 1980 年代的「物件導向程式設計」(Object-Oriented Programming, OOP)。像 Bjarne Stroustrup 的 C++ 或 Alan Kay 的 Smalltalk，它們的「類別」(Class) 就是 ADT 思想的終極體現。一個 class 同時封裝了「資料」（成員變數）和「操作」（成員函式），並透過 public（公開介面）和 private（私有實作）關鍵字，在程式語言層級強制執行了「資訊隱藏」。
到了 1980 年代末，電腦科學的主流已經從「如何寫出巧妙的演算法」轉變為「如何設計出強固的系統架構」。而 ADT，就是這一切的邏輯基石。然而，光有「邏輯上」的整潔還不夠，系統還必須在「實體上」保持高效與穩定。
二、 1980s：平衡樹的黃金年代
- O(log n) 的阿基里斯之踵
1960 年代發明的「二元搜尋樹」(BST)，在「平均」情況下提供了 O(\log n) 的優異查找效率。但在 1970 年代，隨著電腦被用於對可靠性要求極高的商業系統（如銀行帳務），BST 的一個致命缺陷暴露無遺：它的效能極不穩定。
這個缺陷來自於它的「不平衡」。如果資料是隨機插入的，BST 會長得相對茂盛，效能很好。但是，如果資料是「循序」插入的（例如，按照 1, 2, 3... 的順序，或按照字母 A, B, C... 的順序），BST 將會「退化」成一條細長的「鏈結串列」。在這種「最壞情況」下，它的所有操作（查找、插入、刪除）的時間複雜度都會退化到 O(n)。對於一個擁有一百萬筆資料的系統，這意味著一次操作可能需要 1 秒鐘，這在商業上是絕對無法接受的。
因此，整個 1970 年代末到 1980 年代，演算法理論家們的核心任務之一，就是修復 BST 的這個阿基里斯之踵。他們要尋找一種方法，讓這棵樹在任何插入或刪除操作之後，都能自動維持「平衡」狀態，從而「保證」在最壞情況下，效能依然是 O(log n)。這場「平衡樹的競逐」就此展開。
2. 完美的數學家：AVL 樹
最早的解決方案早在 1962 年就由兩位蘇聯數學家 Georgy Adelson-Velsky 和 Evgenii Landis 提出，這就是「AVL 樹」。AVL 樹的平衡規則極其嚴苛：它要求樹中任何一個節點的「左子樹高度」與「右子樹高度」之差，絕對值不能超過 1。這是一棵「完美主義」的樹。
為了維持這種嚴格的平衡，AVL 樹在每次插入或刪除節點後，都必須檢查是否破壞了平衡。一旦發現不平衡，它就會立刻透過一系列稱為「旋轉」(Rotations) 的精妙操作（左旋、右旋、左右旋、右左旋）來重塑樹的局部結構，使其恢復平衡。AVL 樹是第一個實現了「最壞情況 O(log n)」的資料結構，它在數學上是無比優雅的。
然而，它的「完美主義」也成了它的弱點。由於平衡條件太嚴格，即使是很小的插入操作，也可能導致頻繁的「旋轉」，這使得它的「寫入」成本相對較高。雖然它的「查找」效能是所有平衡樹中最快的（因為它最矮、最平衡），但在「插入」和「刪除」密集的場景中，它反而可能比 1960 年代的「不平衡」BST 更慢。它更像是一個數學上的藝術品，而非工程上的實用品。
3. 務實的工程師：紅黑樹 (Red-Black Tree)
如果說 AVL 樹是「完美平衡」，那麼 1970 年代末發展起來的「紅黑樹」就是「足夠好的平衡」。紅黑樹的構想最初由 Rudolf Bayer 在 1972 年提出（他稱之為 "symmetric binary B-tree"），並在 1978 年由 Leonidas J. Guibas 和 Robert Sedgewick 賦予了它「紅黑」的色彩規則並將其發揚光大。
紅黑樹的規則看起來很複雜：1. 節點不是紅色就是黑色；2. 根節點是黑色；3. 所有葉節點（NIL）是黑色；4. 紅色節點的子節點必須是黑色（不能有連續的紅色）；5. 從任一節點到其所有後代葉節點的路徑，都包含相同數量的黑色節點。這些規則的巧妙之處在於，它們共同確保了「最長的路徑（全為紅黑交錯）不會超過最短路徑（全為黑色）的兩倍長」。
這意味著紅黑樹是「大致平衡」的。它不像 AVL 樹那樣嚴格，它允許一定程度的「不平衡」存在。這樣做的好處是巨大的：在插入或刪除時，它需要進行「旋轉」和「重新著色」的機率遠低於 AVL 樹，使得它的「寫入」效能非常出色。紅黑樹在「查找」、「插入」、「刪除」三者之間取得了絕佳的工程平衡。因此，它最終勝出，成為 80 年代至今，系統軟體中最常用的平衡樹：C++ 的 std::map、Java 的 TreeMap、以及 Linux 核心中的許多記憶體管理，都選擇了紅黑樹。
三、 分歧 ：演算法理論 vs. 系統實務
1. 真正的敵人：磁碟 I/O
正當 AVL 樹和紅黑樹在「記憶體」(RAM) 中為了節省 CPU 運算（比較和旋轉）而激戰時，另一場更關鍵的戰役正在「磁碟」(Hard Disk) 上展開。在 1970 年代，資料量開始超越昂貴的記憶體所能容納的極限。例如，銀行的交易紀錄、政府的人口普查資料，必須儲存在容量巨大但速度極慢的「磁碟」上。
這引出了 1970 年代最關鍵的工程洞察：系統的瓶頸不再是「CPU 運算」，而是「I/O（輸入/輸出）」。 CPU 在一秒鐘內可以執行上百萬次計算，但磁碟的磁頭（讀取資料的機械臂）在一秒鐘內可能只能「尋找」資料 100 次。從磁碟讀取 1 位元組，和讀取 4096 位元組（一個「分頁 Page」），在「尋道時間」上幾乎沒有差別。
在這種硬體現實下，紅黑樹的設計簡直是一場災難。紅黑樹是「二元」的，意味著它很高。如果一棵紅黑樹儲存了十億筆資料，它的高度大約是 log_2(10^9)^30 層。這意味著在最壞情況下，要查找一筆資料，電腦需要從磁碟讀取 30 次！以當時的磁碟速度，一次查詢可能需要 1 秒鐘，這足以讓整個銀行系統癱瘓。演算法理論家們在記憶體中追求的 O(log n)，在系統工程師看來，是完全錯誤的優化方向。
2. 為磁碟而生：B 樹 (B-Tree) 的勝利
1970 年，在波音公司工作的 Rudolf Bayer（又是他！）和 Edward McCreight，肩負著為大型資料庫設計索引的任務。他們直面「磁碟 I/O」這個敵人，發明了一種全新的結構——「B 樹」(B-Tree)。B 樹的設計哲學與紅黑樹完全相反：既然讀取一次磁碟的成本很高，那我就讓這一次讀取盡可能地「物超所值」。
B 樹不再是「二元」的，它是「多叉」的。B 樹的一個「節點」不再只儲存 1 個鍵值，而是儲存成百上千個鍵值。這個「節點」的大小，被精確地設計為與磁碟的「分頁」大小（例如 4KB）相對應。這樣，電腦「讀取 1 次」就能把成百上千個鍵值載入到記憶體中。
這導致 B 樹的結構變得極其「矮胖」。例如，一棵階數 (order) 為 1000 的 B 樹，只需要 2 層就能儲存 1000 x 1000 = 100 萬筆資料；只需要 3 層，就能儲存 1000 x 1000 x 1000 = 10 億筆資料！這意味著，無論資料庫有多龐大，B 樹都能保證在 3 到 4 次磁碟 I/O 內找到任何資料。這相較於紅黑樹的 30 次，是指數級的效能提升。B 樹（及其最重要的變體 B+ Tree）因此成為所有現代「關聯式資料庫」（如 Oracle, MySQL, PostgreSQL）索引結構的唯一標準。
3. 兩個世界的成形
這場「平衡樹」的黃金年代，最終在 1980 年代末形成了清晰的分野，這就是「分歧 」。電腦科學家開始在兩個不同的戰場上作戰：
- 演算法理論家 (CPU 戰場)：他們專注於「記憶體內」(in-memory) 的演算法。他們追求數學上的極致與優雅，發明了像 Splay Tree（伸展樹，1985 年）這樣能自我優化的、適用於「快取」(Cache) 的神奇結構。他們的世界是由「CPU 週期」和「時間複雜度」構成的。
- 系統實務家 (I/O 戰場)：他們專注於「硬體友善」(hardware-friendly) 的結構。他們必須與「物理限制」搏鬥，例如磁碟的尋道時間、網路的延遲、CPU 的快取分頁大小。B 樹就是他們最偉大的傑作。他們的世界是由「I/O 次數」、「快取命中率」和「系統吞吐量」構成的。
這場分歧並非分裂，而是「成熟」。它標誌著「電腦科學」不再是一個單一的學科，而是演化出了「理論電腦科學」和「電腦系統工程」兩個同樣深刻、同樣重要的分支。從 1970 到 1990，我們學會了如何用「抽象」來管理邏輯，用「平衡」來保證效能，更學會了「向硬體妥協」來打造真正強固的系統。這套工程化的紀律，為即將到來的 1990 年代——那個屬於「網路」和「海量資料」的時代——做好了萬全的準備。
