这是一个创建于 1358 天前的主题，其中的信息可能已经有所发展或是发生改变。
虽然自己对数据库并没有深入了解，但看到帖子 “一个非常复杂的需求，如何设计表结构” ，感觉数据库还是挺有意思的。想聊聊自己的思考，抛砖引玉。
上面这个帖子，提到的问题是比较经典的树状节点的查找、修改。从中可以明显地感受到操作“内存对象”和操作“关系型数据库数据”的差异——内存中，对象之间可以互相指向，像是修改子节点结构、查找子节点，这些操作都可以很直接，顺着节点的指向，可以很自然很快地完成想要的操作，数据的一致性也很容易保证。而关系型数据库存储则只能通过“查表”这种间接方式，远远没有操作内存对象那样直接快速，还要考虑各个表中的数据一致性。
虽然看起来内存对象和数据库数据的形式差异太大了，但追根溯源，最根本的差异可能就只有一个：
- 内存对象因为在内存中，因此是可以随机访问的，可以用指针(实体)，以 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)的时间复杂度应该是可以优化的。这引出了一个问题，怎么通过改进表结构，来优化数据库的性能呢，而这种优化有没有规律可循呢？
 |
1
darksword21 2021-03-31 17:50:45 +08:00
一楼蹲，一楼蹲完了
|
 |
2
Hieast 2021-03-31 17:50:57 +08:00
可以了解一下图数据库
|
 |
3
nulIptr 2021-03-31 18:21:50 +08:00
思考问题的时候一定要考虑场景
古时候内存没那么大，硬盘访问速度也很慢。现在看起来没那么大的数据量那时候处理起来也比较麻烦。 抛开物理机性能不谈关系型数据库还要有 acid 特性。 大学里教数据结构的老师一般都会说一句，自己实现是数据结构比 stl 快很正常，因为 stl 要处理各种情况以适应各种各样的场景，而你只需要处理你这块的问题。 我敢说任何键值型数据库查询速度都不如各种语言内置的 Map 结构。那又如何呢，这俩根本不是一个等级的东西啊。你正文举例的内存对象和数据库怎么比？关系型数据库查询最终不也是落在数据结构的查询上面？ |
 |
4
xupefei 2021-03-31 18:29:14 +08:00 via iPhone  1
看了几遍没看懂在说啥…我觉得楼主把数据库索引和真正的数据搞混了
|
 |
5
tabris17 2021-03-31 18:30:58 +08:00 via iPhone
没错对象持久化储存不一定要用到关系数据库
|
 |
6
auxox 2021-03-31 19:04:05 +08:00
所以文档数据库不能解决这个问题吗。
|
 |
7
hxndg 2021-03-31 22:56:20 +08:00
？？？？？？？？？坦白说我没看懂你在说啥？
你再说索引？还是文档模型和关系模型？抑或说图数据库？ 而且表的结构和索引也不是必然联系？ 而且内存对象可以随机访问，关系数据库不能随机访问这个事情（你说的该是硬盘吧，关系数据库不是完全不能随机访问的） 建议先看看《数据密集型系统设计》前三章？ |
 |
8
sillydaddy OP |
|
9
hxndg 2021-04-01 13:54:51 +08:00
@sillydaddy
首先，数据结构和关系型数据库没有必然联系， 其次，关系型数据库是可以放一部分在内存里的， 你需要区分开抽象层面和实现层面，不要混为一谈，先找点资料查询一下， 最后，内存里面就随机访问？你说的是什么，是 hash 吧. 你再看看 SSTables ？ 有序性的思考应该集中在数据结构层面，而不是上层抽象上。 |
Select Language