4

我是数据库新手。我想知道数据库中的一些事情。例如，我看到了 Facebook 如何存储朋友关系的结构（参见：https ://developers.facebook.com/docs/reference/fql/friend ）。只有两列，第一个用户 id 和第二个用户 id。那没关系。

正如维基百科所说，Facebook 拥有大约 10 亿活跃用户。所以在那个朋友关系表中，可能有大约 1000 亿行。搜索该表非常快（例如：查看我的朋友列表）。我想知道他们是如何以这种速度做到的。

是因为 Facebook 有一些神奇的后端吗？还是数据库的魔力？我也可以使用 PHP 和 MySQL 来做（拥有数百万用户并在几秒钟内搜索数据库）吗？

（我可能会问一个愚蠢的问题，但它总是困扰我知道，请留下答案）

4

3 回答 3

2

数据库使用索引。通过这种方式，它可以快速找到与给定用户 ID 相关的数据。

根据索引结构、空间占用等...有一个好处，即不是搜索 N 列，而是搜索 - 例如 - log(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 次尝试），但您也可以通过二分法进行

  • 你：5000
  • 玩家：+
  • 7500 或 (10000 - 5000)/2
  • -
  • 6250 或 (7500 - 5000)/2
  • -
  • ETC...

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

--

关于对数

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

于 2013-02-03T16:42:18.237 回答
1

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

于 2013-02-03T16:41:28.423 回答
0

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

于 2013-02-03T16:43:02.643 回答