在海量数据库中搜索的速度

Question

我是数据库的纽比。我对数据库中的一些东西感到好奇。例如，我看到了Facebook如何存储朋友关系的结构(参见：https://developers.facebook.com/docs/reference/fql/friend)。只有两列，第一个用户id和第二个用户id。好吧，那没问题。

正如维基百科所说，facebook大约有10亿活跃用户。因此，在朋友关系表中，可能有大约1000亿行。在那张表中搜索非常快(例如:查看我的朋友列表)。我想知道他们是怎么以这样的速度做到的。

是不是因为Facebook有一些神奇的后端？或者是数据库的魔力？我是否也可以使用PHP和MySQL来做这件事(拥有数以百万计的用户并在几秒钟内搜索数据库)？

(我可能问了一个愚蠢的问题，但知道这一点总是困扰我，请留下答案)

Answer 1

数据库采用indexes。通过这种方式，它可以快速找到与给定userID相关的数据。

取决于索引结构、空间占用等。这有一个好处，例如，它搜索log(N)，而不是搜索N列。千亿行的二分法搜索

N = 100,000,000,000

将会是

Search(N) : search log2(N) = search (36 rows)

而不是搜索10^12行，只需要分析36行。

在你提到的情况下，朋友，每个用户可能有几个朋友，所以

user1 => (userX, userY, userZ, ...)
userX => (userU, userV, user1, ...)

这意味着user1是userX，userY等的朋友。也就是说，你对每个用户没有唯一的索引。但是每两个用户有一个唯一的索引。

在Mysql上，这将是

UNIQUE(user1,user2)

这意味着这对情侣(user1，user2)只在表中出现一次。语法应该是

CREATE UNIQUE INDEX friendsindex ON friends(user1,user2)

friendsindex是索引名，friends是表。或者如您所说，将表主键声明为(user1,user2) (每个表的主键是唯一的)。

--

赢得游戏的策略包括找到给定对象的确切价格，这是基于相同的原则。假设价格在1到10000之间。你说出一个价格，管理员就会说+或-。你必须在尽可能少的尝试中找到价格。价格是6000英镑。

你可以从1开始，给出直到6000的所有价格(即6000次尝试)，但你也可以通过二分法进行

• you: 5,000
• 游戏玩家：+
• 7500或(7500 - 5000)/2
• -
• etc...

或(7500-

在每次迭代时，将剩余范围除以2。您可以在12次尝试中查找，而不是6000次尝试(log2(6000))。

--

关于logarithms

例如，如何在2^x = 1024中查找x？或者x = log2(1024)表示以2为底的1024的对数(答案: 10)。在我们的故事中，一个具有基于二叉树的索引的1024行表将需要10次尝试(最大)来找到正确的元素(而不是1024最大)。

Answer 2

性能可能来自索引、缓存和sharding。

Answer 3

Facebook有一个服务器群。我认为他们设置了一个集群或其他东西来拥有几个相同的sql服务器副本。在这些sql数据库中，他们使用索引进行更快的搜索，但他们也可以使用用户计算机上的本地现金，这有助于他们获得更快的结果。