微博、微信那个“图”怎么存放的呢？

微博、微信是两种“图”，前者的关注好友属于有向图，后者是无向图。

数据结构是为算法服务的，所以具体选择哪种存储方式，与期望支持的操作有关系，在微博中，假设我们需要支持下面几种操作：

• 判断用户 A 是否关注了用户 B
  
• 判断用户 A 是否是用户 B 的粉丝
  
• 用户 A 关注用户 B
  
• 用户 A 取消关注用户 B
  
• 根据用户名称的首字母排序，分页获取用户的粉丝列表；
  
• 根据用户名称的首字母排序，分页获取用户的关注列表
  

存储一张图有两种主要的存储方法，邻接矩阵和邻接表，因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间，所以这里使用邻接表存储。

一个邻接表存储有向图，很容易查询某个用户关注了哪些用户，但是如果想知道某个用户被哪些用户关注，就十分困难。

因此，我们需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。对应在图上，邻接表中，每个顶点的链表中，存储的是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。查询某个用户关注了哪些用户，我们可以在邻接表中查找，如果查询某个用户被哪些用户关注了，我们从逆邻接表中查找。

基础的邻接表不适合快速判断两个用户之间是否是关注和被关注的关系，所以可以使用改进版本，将邻接表中的链表改成支持快速查找的动态数据结构。红黑树、跳表、有序动态数据还是散列表？

因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。因为跳表的插入、删除、查找都非常高效，时间复杂度是O(logn)，空间复杂度上比较高，是O(n)，最重要的一点是，跳表中存储的数据本来就是有序的，分页获取粉丝列表或者关注列表，就非常高效。

对于小规模的数据，我们可以将整个社交关系存放在内存中，但是数据规模太大，我们就无法全部存储在内存中，这时候该怎么办呢

我们可以使用哈希算法将数据分片处理，将邻接表存储在不同的机器上，比如机器 A 存储顶点 1,2,3 的邻接表，在机器 B 上存储顶点 4,5 的邻接表。逆邻接表的处理方式也一样。当要查询顶点与顶点的关系时，我们利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。

除此之外，我们还可以使用硬盘存储数据，比如使用数据库的存储方式，并在表上建立多个索引。