1990 年，提姆·柏內茲-李 (Tim Berners-Lee) 在 CERN 寫下了全球資訊網 (World Wide Web) 的第一個標準。1993 年，Mosaic 瀏覽器誕生，讓網際網路從學術象牙塔走入了尋常百姓家。隨之而來的，是人類歷史上從未有過的資訊大爆炸。一夜之間，資料的來源不再只是企業內部的會計系統或人事部，而是來自全球數百萬個網站、數億次點擊、以及無盡的超連結。
1980 年代的工程師們剛為「磁碟 I/O」這個敵人（B 樹）找到了完美的解決方案，卻立刻迎來了一個更恐怖的對手：「網路延遲」與「資料規模」。問題變了。問題不再是「如何在一台機器的 1TB 硬碟上，用 3 次 I/O 找到一筆資料？」；問題變成了「如何在散布於全球的一萬台廉價 PC 上，儲存 1000TB 的網頁，並在 0.5 秒內回應使用者的搜尋請求？」
這個十年，是「單機」思維的黃昏，也是「分散式」思維的黎明。傳統資料結構被迫在兩個戰場上同時作戰：一些結構在「單機」的舊世界中被淬鍊到極致，而另一些結構則被「魔改」甚至「重塑」，以適應「多機」的新世界。這場關於「可擴展性」(Scalability) 的挑戰，就此拉開序幕。
一、 單機的極致：B+ 樹與資料庫的黃金年代
1. 關聯式資料庫的「最後一哩路」
在 1990 年代，雖然網際網路是鎂光燈下的明星，但全球商業的真正霸主，是「關聯式資料庫管理系統」(RDBMS)。Oracle、IBM DB2、Microsoft SQL Server、Sybase，這些巨頭掌控著所有企業的核心命脈——交易、庫存、客戶資料。對它們而言，最重要的不是「無限擴展」，而是「絕對的穩定」與「高效的查詢」。它們的世界，是「垂直擴展」(Scale-Up) 的世界：當效能不夠時，就購買更昂貴、更強大的伺服器（例如 Sun Microsystems 的大型主機）。
在這個「單機巨獸」的思維下，1970 年代的 B 樹暴露出了一個小小的、但對資料庫至關重要的缺陷。B 樹的設計目標是「快速查找」單一鍵值（O(log_k n)）。但是，資料庫的查詢遠不止於此，它們需要進行大量的「範圍掃描」(Range Scan)，例如 SELECT * FROM users WHERE age > 30 或 SELECT SUM(salary) FROM employees。
在 B 樹上執行這種「範圍掃描」，是一場效能噩夢。由於 B 樹的資料分散儲存在所有節點（內部節點與葉節點）中，要找到所有 age > 30 的資料，指標需要在樹的各個層級中「上下來回」移動，進行複雜的中序遍歷，這會產生大量的隨機磁碟 I/O。B 樹的設計者專注於「點查詢」，卻忽視了「線查詢」。
2. B+ 樹：為「掃描」而生的終極進化
為了解決這個問題，B 樹的一個關鍵變體——「B+ 樹」——在 1990 年代的資料庫引擎中取得了絕對的統治地位。（B+ 樹的概念在 1970 年代末由 Douglas Comer 在其經典論文《The Ubiquitous B-Tree》中被清晰定義，但在 80-90 年代才成為業界標配）。B+ 樹的改動是如此精妙，它完美地平衡了「查找」與「掃描」這兩種需求。
B+ 樹做出了兩個關鍵的改變：第一，只有「葉節點」(Leaf Nodes) 才真正儲存資料（或指向資料的指標）；所有的「內部節點」都只儲存「索引鍵值」（路標），不存資料。這使得內部節點變得更小，B 樹的「階數」可以更高，樹因此變得更「矮胖」，點查詢的 I/O 次數甚至可能比 B 樹更少。
第二，也是最重要的一點：B+ 樹的所有「葉節點」，會透過「指標」串連成一個「雙向鏈結串列」。這是一個天才般的設計。當資料庫需要執行 age > 30 的範圍掃描時，它首先像 B 樹一樣進行一次點查詢，找到 age = 30 的那個葉節點。然後，它不再需要回到上層節點，而是直接沿著葉節點的「鏈結串列」，一路「水平」掃描下去，直到 age 的盡頭。這將原本的「隨機 I/O」變成了極速的「循序 I/O」，效能提升了數十倍。
3. 「結構」對「硬體」的完美適應
B+ 樹的勝利，是 1980 年代「系統實務」派的終極勝利。它不追求 AVL 樹那樣的「數學完美」，而是追求對「磁碟硬體」的「物理完美」。它的「節點大小」對應磁碟的「分頁大小」，它的「多叉結構」為了減少「I/O 次數」，它的「葉節點鏈結」為了迎合磁碟的「循序讀取」優勢。
在 1990 年代，B+ 樹成為所有 RDBMS（包括開源的 MySQL、PostgreSQL）儲存引擎的絕對核心，它象徵著「單機資料結構」在理論和工程上所能達到的最高成就。然而，它也像一座精美的水晶宮殿，被牢牢地鎖死在了「單機」的邊界之內。它的複雜結構和對循序 I/O 的依賴，使得它幾乎不可能被「橫向擴展」到一千台機器上。當 B+ 樹在舊世界登基為王時，新世界已經在尋找全新的出路。
二、 當資料有了「空間」：R-Tree 與 GIS 的覺醒
1. 一維索引的侷限
B+ 樹能完美索引「一維」資料，例如 employee_id、age 或 name（按字典序）。但是，1990 年代的新應用程式開始提出「多維」的問題。地理資訊系統 (GIS) 開始崛起，MapQuest 網站 (1996) 讓普通人也能在網路上查詢地圖。這些系統的核心問題是：「請找出離我目前位置方圓 1 公里內的所有咖啡廳」或「找出所有與這條河流相交的土地」。
B+ Tree 面對這個問題束手無策。你不能用一個 B+ 樹同時索引「經度」和「緯度」。你可以建立一個經度索引和一個緯度索引，但這樣查詢「一個方塊區域」時，你需要分別查詢兩個索引，然後在記憶體中取交集，效能極差。這個問題需要一個全新的資料結構，一個原生支援「多維空間」的索引。
1984 年，加州大學柏克萊分校的 Antonin Guttman 發表了「R 樹」(R-Tree) 的論文，但在當時，它更像是一個學術上的發明。直到 1990 年代，隨著 GIS 系統和多媒體資料庫（例如儲存圖片特徵）的商業化，R 樹才真正從論文走入工業界，成為 Oracle Spatial 等空間資料庫的核心。
2. B 樹在「多維」的投影
R 樹的設計思想，是 B 樹在多維空間的巧妙延伸。B 樹將一維的「數線」切割成不重疊的「線段」（例如 [1-10], [11-20]）；而 R 樹則將二維（或多維）的「平面」切割成一個個「矩形」區域。R 樹的葉節點儲存的是「真實物件」（例如咖啡廳的座標）的「最小邊界矩形」(Minimum Bounding Rectangle, MBR)。
R 樹的「內部節點」，則儲存著一個更大的 MBR，這個 MBR 剛好能「包住」它所有「子節點」的 MBR。這樣，一棵 R 樹就建立了一個空間上的層級結構。當你要查詢「方圓 1 公里內」（一個圓形區域）的咖啡廳時，你從根節點開始。你檢查根節點下的 MBRs，只進入那些「與你的查詢圓形相交」的子節點，而「剪掉」所有不相交的 MBRs。
R 樹（及其後來的變體 R* 樹、R+ 樹）的出現，標誌著資料結構開始從處理「數字」和「文字」，擴展到處理「空間」、「形狀」和「位置」。它和 B+ 樹一樣，都是「系統實務」派的傑作，它們都針對 I/O 進行了優化，都是「矮胖」的多叉樹。它證明了 B 樹的偉大思想，可以被「投影」到更高維度的世界。
三、 當「關係」成為「資料」：圖 (Graph) 理論的逆襲
1. 網際網路：世界上最大的「圖」
1960 年代，高德納 (Donald Knuth) 將「圖」(Graph) 作為一種「邏輯模型」引入了電腦科學。但在隨後的幾十年裡，圖大多只存在於學術界，用於解決網路流量、電路佈局等專門問題。但在 1990 年代，人類親手建造了一個有史以來最龐大、最真實的「圖」——全球資訊網。
這個洞察，是 1990 年代中後期最重要的思想之一。網際網路的本質，就是一個「有向圖」：每一個「網頁」是一個「頂點」(Node)，而每一個「超連結」 (<a href..._) 就是一條「有向邊」(Edge)。這個圖的規模史無前例，它擁有數十億個頂點和數千億條邊。
早期的搜尋引擎，如 AltaVista (1995)，只是把網際網路當作一個巨大的「文件庫」。它們使用傳統的「倒排索引」(Inverted Index) 來索引網頁上的「關鍵字」，但它們無法判斷「品質」。它們只知道某個詞出現了，卻不知道這個網頁「重不重要」。這導致搜尋結果中充斥著大量的垃圾資訊。
2. PageRank：用「圖」來定義「權威」
1996 年，史丹佛大學的兩位博士生——賴利·佩吉 (Larry Page) 和謝爾蓋·布林 (Sergey Brin)——有了一個革命性的想法：一個網頁的重要性，不該由它「自己說了算」（它用了多少關鍵字），而該由「別人說了算」（有多少「重要」的網頁連結到它）。這是一個源自學術論文引用的古老概念，但他們第一次將其應用到整個網際網路圖上。
他們提出的「PageRank」演算法，是一個純粹的「圖論」演算法。它 iteratively（迭代地）計算每個網頁的「權威分數」：一個網頁的分數，等於所有「連結到它」的網頁的分數，按比例分配後的總和。這本質上是在求解一個巨型稀疏矩陣的「特徵向量」(Eigenvector)。PageRank 的成功（Google 的核心秘密武器），是「圖」結構從「邏輯模型」走向「商業應用」的最強訊號。
在 1990 年代末，圖的應用也開始在其他領域萌芽。AI 研究者開始構建「知識圖譜」(Knowledge Graph)（當時尚未如此命名），用圖來表示實體（如「台北 101」）及其關係（如「位於」->「信義區」）。而 1997 年上線的 https://www.google.com/search?q=SixDegrees.com，更是直接將「人」作為頂點，「朋友關係」作為邊，創造了「社會網路圖」(Social Graph) 的雛形。圖，不再是演算法教科書上的抽象概念，它正在成為這個時代最重要的「資料本身」。
四、 分歧 4：單機結構 vs. 橫向擴展 (Scalability)
1. 「巨獸」的黃昏
1990 年代末，網際網路的巨頭們——Yahoo!、Google、eBay、Amazon——同時撞上了一堵高牆。這堵牆，就是「單機」的物理極限。B+ 樹索引再快，R 樹空間切割再妙，它們都只能運行在一台「超級伺服器」上。但當時最強大的伺服器，也無法裝下整個網際網路的索引，更無法承受全球每秒數十萬次的搜尋請求。
「垂直擴展」(Scale-Up) 的道路走到了盡頭。唯一的出路，是「水平擴展」(Scale-Out)：用上千台、上萬台廉價的 PC 伺服器，組成一個「叢集」(Cluster)，共同儲存資料、分攤運算。這就是「分散式系統」(Distributed Systems) 的黎明。
這個全新的架構，對 1980 年代建立起來的資料結構（如 B+ 樹）判了死刑。B+ 樹那種高度複雜、緊密耦合、依賴循序儲存的結構，根本無法被「劈開」分散到一萬台機器上。如果 user_id = 100 在 A 機器，user_id = 101 在 B 機器，B+ 樹的「葉節點鏈結串列」就徹底斷裂了。系統需要一種全新的、更「粗暴」、更「簡單」的結構，來適應這種「Shared Nothing」（無共享）的架構。
2. 雜湊表 (Hash Table) 的王者歸來
工程師們在 1960 年代的故紙堆裡，找到了答案——「雜湊表」(Hash Table)。雜湊表，這個在 1980 年代被 B 樹擊敗（在資料庫領域）、只能存活於記憶體（如編譯器符號表）的老舊結構，突然在新世界裡獲得了新生。
為什麼？因為雜湊表天生就是「可分散」的。它的核心是一個「雜湊函式」，f(key) -> index。在分散式系統中，這個函式被稍加修改：f(key) -> server_id。例如，Google 要儲存 100 億個網頁，它有 1 萬台伺服器。當一個新網頁 (URL) 進來時，它只計算 hash(URL) % 10000 = server_id（例如 4567），然後就把這個網頁的資料「丟」給第 4567 號伺服器。
這就是「分散式雜湊索引」(Distributed Hash Index) 的原型。它實現了近乎完美的「水平擴展」：當資料量加倍時，伺服器數量也加倍，% 10000 改成 % 20000 即可（當然，實際的「一致性雜湊」演算法更複雜）。它的查找效能也是 O(1)：只需要一次雜湊計算、一次網路跳轉，就能直達目標伺服器。
3. 「結構」與「擴展性」的根本權衡
1990 年代末，這場「分歧 4」變得無比清晰。這是一場「結構的複雜性」與「系統的可擴展性」之間的根本權衡。
- B+ 樹 (結構派)：它擁有豐富的「結構」，提供了強大的查詢能力（點查詢、範圍掃描、排序）。但它犧牲了「可擴展性」。它適用於單機的、資料高度結構化、需要複雜查詢的「系統實務」（如 90 年代的 RDBMS）。
- 分散式雜湊 (擴展派)：它幾乎「沒有結構」（只有鍵值對 Key-Value）。它犧inda牲了「所有」B+ 樹的能力（無法範圍掃描、無法排序）。但它換來了「無限的可擴展性」。它適用於分散式的、資料量無上限、只需要簡單鍵值查詢的「網路實務」（如 90 年代末的搜尋引擎底層）。
這個分歧是如此深刻，它直接定義了 2000 年代的主旋律。B+ 樹的世界，演變成了「SQL」的世界；而分散式雜湊的世界，則引爆了「NoSQL」（Not Only SQL）運動。1990 年代，這個承上啟下的十年，在舊世界的頂峰（B+ 樹）畫上了句號，並為新世界（Scalability）寫下了序章。
