一、QQ這種大型數(shù)據(jù)庫是怎么實(shí)現(xiàn)數(shù)據(jù)瞬間查詢的

不要總覺得大型互聯(lián)網(wǎng)公司的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)會(huì)有多復(fù)雜。實(shí)際上簡單得很，大部分都比你在大學(xué) SQL 課上創(chuàng)建的數(shù)據(jù)庫還要簡單。越核心的數(shù)據(jù)，其存儲(chǔ)結(jié)構(gòu)越簡單。簡單的才可靠。

像 QQ 這種，最核心的數(shù)據(jù)，一是用戶信息，二是好友關(guān)系。我可以打包票，它們的存儲(chǔ)結(jié)構(gòu)只會(huì)是最簡單的 key-value 格式，不會(huì)有第二種選擇。

至于 key-value 怎么保存在內(nèi)存或者硬盤上，倒是可以有多種選擇，哈希表或者樹狀結(jié)構(gòu)或者你想搞 LSM tree 什么的都可以，但是都不會(huì)超過大二的知識(shí)點(diǎn)。

舉個(gè)例子，根據(jù) QQ 號(hào)查用戶信息。Key 是 QQ 號(hào)、value 是用戶信息，就完了。

什么，你說還要按昵稱查詢、按郵箱查詢？簡單，每種查詢條件再來一個(gè) key，用 key-value 格式再保存一個(gè) “昵稱–>QQ號(hào)” “郵箱–>QQ號(hào)”的映射。這些核心數(shù)據(jù)都是讀量遠(yuǎn)大于寫量，所以不會(huì)在乎寫的時(shí)候多寫幾個(gè) key，要的是讀快。

再比如說，好友關(guān)系。這也好說，每個(gè)用戶一個(gè) key，value 就是他的好友 ID 列表（排好序）。查好友的時(shí)候直接按用戶拉出他的好友列表。查共同好友？把兩個(gè)用戶的好友列表都拉出來做交集，都是排好序的，取交集也就是 O(n) 的復(fù)雜度。

加好友的時(shí)候怎么辦？往兩邊用戶的 key 都寫啊。讀量遠(yuǎn)大于寫量，寫不怕麻煩，只要讀快就行。

（公眾號(hào)、微博這種帶有 B2C 特性的關(guān)系鏈會(huì)復(fù)雜一點(diǎn)，因?yàn)殛P(guān)注者數(shù)量無上限。）

好了，存儲(chǔ)格式定下來了，再說怎么查。

畢竟查詢量巨大，一臺(tái)機(jī)器扛不住，那就分多臺(tái)。把 key 分一下段、或者哈希一下，分散到多臺(tái)機(jī)器上，每臺(tái)機(jī)器只保存全量數(shù)據(jù)的一部分。

基本原理就是這樣，沒有什么特別玄乎的東西。

實(shí)際工程上的努力，基本都在保證可用性和一致性上面。

可用性：機(jī)器多了，總有機(jī)器會(huì)死機(jī)，有硬盤會(huì)壞，有機(jī)房會(huì)掉電，有光纜會(huì)被挖斷。怎么辦？每份數(shù)據(jù)都存多份，放到多臺(tái)機(jī)器上。保存相同數(shù)據(jù)的機(jī)器分布到多個(gè)機(jī)房甚至多個(gè)城市，不可能大家一起壞。當(dāng)然， 這樣寫的時(shí)候會(huì)麻煩點(diǎn)，別忘了，大多數(shù)數(shù)據(jù)都是讀多寫少的，寫不怕麻煩。

一致性：同一份數(shù)據(jù)在多機(jī)保存了多份以后，就得保證不能出現(xiàn)不一致的數(shù)據(jù)。這個(gè)才是最難的。

在互聯(lián)網(wǎng)公司里，要想見到復(fù)雜的表結(jié)構(gòu)、復(fù)雜的 JOIN、FOREIGN KEY 等，最可能的是在內(nèi)部系統(tǒng)里面。內(nèi)部系統(tǒng)的開發(fā)，在互聯(lián)網(wǎng)的工程師里面是處于鄙視鏈比較低端的……

延伸閱讀：

二、數(shù)據(jù)庫的查詢功能實(shí)現(xiàn)原理

數(shù)據(jù)庫查詢是數(shù)據(jù)庫的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫系統(tǒng)的設(shè)計(jì)者會(huì)從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時(shí)顯然是糟糕的，好在計(jì)算機(jī)科學(xué)的發(fā)展提供了很多更優(yōu)異的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會(huì)發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時(shí)將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。