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

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

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

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

• 内存对象因为在内存中，因此是可以随机访问的，可以用指针(实体)，以 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)的时间复杂度应该是可以优化的。这引出了一个问题，怎么通过改进表结构，来优化数据库的性能呢，而这种优化有没有规律可循呢？