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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

延伸閱讀：

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

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