关于内存对象与关系型数据库的思考

虽然自己对数据库并没有深入了解，但看到帖子 “一个非常复杂的需求，如何设计表结构” ，感觉数据库还是挺有意思的。想聊聊自己的思考，抛砖引玉。

上面这个帖子，提到的问题是比较经典的树状节点的查找、修改。从中可以明显地感受到操作“内存对象”和操作“关系型数据库数据”的差异——内存中，对象之间可以互相指向，像是修改子节点结构、查找子节点，这些操作都可以很直接，顺着节点的指向，可以很自然很快地完成想要的操作，数据的一致性也很容易保证。而关系型数据库存储则只能通过“查表”这种间接方式，远远没有操作内存对象那样直接快速，还要考虑各个表中的数据一致性。

虽然看起来内存对象和数据库数据的形式差异太大了，但追根溯源，最根本的差异可能就只有一个：

内存对象因为在内存中，因此是可以随机访问的，可以用指针(实体)，以 O(1)的速度直接访问对象、修改对象的数据；
而关系型数据库，是不能提供随机访问的(为什么不能有随机访问的特性呢？)。要找到某条数据，至少需要以关键字作 O(lgN)的查表运算；

可以想象一下，在上面的帖子中，如果将内存对象节点树，照搬到关系型数据库中，表结构应该是这样的：

id, parent_id, children_ids

上面的表结构，在内存对象与数据库记录之间建立了一种对应。对内存对象的操作，可以简单的映射到对数据库记录的操作，只不过复杂度倍增了 O(lgT)。

例如对于查找某个节点的所有子节点这个操作，

如果在内存中操作，递归查找出所有的子节点，是 O(N)的复杂度，N 是所有子节点的数量。
而如果在数据库中，递归查找出所有的子节点，就变成了 O(N)*O(lgT)，其中 T 是表中的记录总数量，因为每个子节点，都需要搜索 id 为关键字的整个表，每次查找都需要 O(lgT)的时间。

但 O(N)*O(lgT)的时间复杂度应该是可以优化的。这引出了一个问题，怎么通过改进表结构，来优化数据库的性能呢，而这种优化有没有规律可循呢？

nulIptr

2021-03-31 18:21:50 +08:00

思考问题的时候一定要考虑场景
古时候内存没那么大，硬盘访问速度也很慢。现在看起来没那么大的数据量那时候处理起来也比较麻烦。
抛开物理机性能不谈关系型数据库还要有 acid 特性。

大学里教数据结构的老师一般都会说一句，自己实现是数据结构比 stl 快很正常，因为 stl 要处理各种情况以适应各种各样的场景，而你只需要处理你这块的问题。

我敢说任何键值型数据库查询速度都不如各种语言内置的 Map 结构。那又如何呢，这俩根本不是一个等级的东西啊。你正文举例的内存对象和数据库怎么比？关系型数据库查询最终不也是落在数据结构的查询上面？

sillydaddy

2021-04-01 13:31:34 +08:00

@Hieast
@hxndg
@auxox
图数据库？文档数据库？好的，我去了解一下。

@tabris17 #4 > “我觉得楼主把数据库索引和真正的数据搞混了”
没有吧，你可以看一下主题里提到的那个帖子。一个树形结构，如果使用内存对象，那么查找和修改的算法分别可以在 O(N)和 O(1)的时间复杂度完成。而使用关系型数据库，应该是达不到这个时间复杂度的，至少不能同时达到。

@hxdng #7 > “你说的该是硬盘吧，关系数据库不是完全不能随机访问的”
有可以随机访问的关系型数据库吗？这块不了解，可以举个例子吗？