V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sillydaddy
V2EX  ›  数据库

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

  •  1
     
  •   sillydaddy · 2021-03-31 17:48:29 +08:00 · 1245 次点击
    这是一个创建于 1093 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    9 条回复    2021-04-01 13:54:51 +08:00
    darksword21
        1
    darksword21  
       2021-03-31 17:50:45 +08:00
    一楼蹲,一楼蹲完了
    Hieast
        2
    Hieast  
       2021-03-31 17:50:57 +08:00
    可以了解一下图数据库
    nulIptr
        3
    nulIptr  
       2021-03-31 18:21:50 +08:00
    思考问题的时候一定要考虑场景
    古时候内存没那么大,硬盘访问速度也很慢。现在看起来没那么大的数据量那时候处理起来也比较麻烦。
    抛开物理机性能不谈关系型数据库还要有 acid 特性。

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

    我敢说任何键值型数据库查询速度都不如各种语言内置的 Map 结构。那又如何呢,这俩根本不是一个等级的东西啊。你正文举例的内存对象和数据库怎么比?关系型数据库查询最终不也是落在数据结构的查询上面?
    xupefei
        4
    xupefei  
       2021-03-31 18:29:14 +08:00 via iPhone   ❤️ 1
    看了几遍没看懂在说啥…我觉得楼主把数据库索引和真正的数据搞混了
    tabris17
        5
    tabris17  
       2021-03-31 18:30:58 +08:00 via iPhone
    没错对象持久化储存不一定要用到关系数据库
    auxox
        6
    auxox  
       2021-03-31 19:04:05 +08:00
    所以文档数据库不能解决这个问题吗。
    hxndg
        7
    hxndg  
       2021-03-31 22:56:20 +08:00
    ?????????坦白说我没看懂你在说啥?

    你再说索引?还是文档模型和关系模型?抑或说图数据库?

    而且表的结构和索引也不是必然联系?

    而且内存对象可以随机访问,关系数据库不能随机访问这个事情(你说的该是硬盘吧,关系数据库不是完全不能随机访问的)

    建议先看看《数据密集型系统设计》前三章?
    sillydaddy
        8
    sillydaddy  
    OP
       2021-04-01 13:31:34 +08:00
    @Hieast
    @hxndg
    @auxox
    图数据库?文档数据库? 好的,我去了解一下。


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

    @hxdng #7 > “你说的该是硬盘吧,关系数据库不是完全不能随机访问的”
    有可以随机访问的关系型数据库吗?这块不了解,可以举个例子吗?
    hxndg
        9
    hxndg  
       2021-04-01 13:54:51 +08:00
    @sillydaddy

    首先,数据结构和关系型数据库没有必然联系,
    其次,关系型数据库是可以放一部分在内存里的,
    你需要区分开抽象层面和实现层面,不要混为一谈,先找点资料查询一下,
    最后,内存里面就随机访问?你说的是什么,是 hash 吧. 你再看看 SSTables ?

    有序性的思考应该集中在数据结构层面,而不是上层抽象上。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1198 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 23:20 · PVG 07:20 · LAX 16:20 · JFK 19:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.