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

关于 B+树索引的问题

  •  
  •   zxCoder · 2020-12-21 19:20:57 +08:00 · 1790 次点击
    这是一个创建于 1418 天前的主题,其中的信息可能已经有所发展或是发生改变。

    数据库一个 page 存放一个树节点的话,那么树的阶数(order)是不是得根据键的不同类型来确定,比如小的键,一个 page 也就是一个节点可以放更多的键。还是说整个数据库的 B+树索引阶数都是固定的,而节点的大小不固定

    10 条回复    2020-12-21 21:48:30 +08:00
    nthhdy
        1
    nthhdy  
       2020-12-21 19:38:57 +08:00
    我的理解是,前者是对的,节点的大小是固定的。每条记录(或者索引)占用空间小,节点就可以放更多的记录。树的高度就倾向于比较小,查询会相对快。
    geebos
        2
    geebos  
       2020-12-21 19:52:40 +08:00
    节点的大小是可变的,节点越大,单个 page 可存储的节点就越少,反之则越多。

    参考: https://dev.mysql.com/doc/internals/en/innodb-fil-header.html
    auxox
        3
    auxox  
       2020-12-21 20:09:18 +08:00
    数据库系统中 B 树没有固定的阶。我认为不用固定阶的原因是很难计算一个 page 能存放多少记录,因为很多记录是变长的。因此对于大部分采用 B 树实现的存储系统来说,它们只是当 page 装不下新插入的记录时,就会分裂。当 page 比较'空旷'时就会 merge 。另外,并不是所有的基于 B 树的存储引擎都采用固定大小的 page 。
    geebos
        4
    geebos  
       2020-12-21 20:16:02 +08:00
    andj4cn
        5
    andj4cn  
       2020-12-21 20:26:06 +08:00
    应该 page 大小是固定的,page 除了保存头信息外,剩下的空间保存指向子 page 的 KV 指针。指针 pair 的大小是内置的,page 大小也是固定的。我的理解是,每个 page 能保存的最大子 page 指针对也是固定的。达到最大值则该 page 分裂,小于 B+ 树的要求则合并。
    zxCoder
        6
    zxCoder  
    OP
       2020-12-21 20:29:26 +08:00
    @andj4cn 索引的 key 大小应该是不固定的吧我觉得,比如一个 int 和一个 bigint,同一个 page 来存这些 key,应该数量会不一样
    zxCoder
        7
    zxCoder  
    OP
       2020-12-21 20:33:30 +08:00
    @auxox “数据库系统中 B 树没有固定的阶。我认为不用固定阶的原因是很难计算一个 page 能存放多少记录” 这句话我不太能理解,我的理解是,如果不是固定的阶,不就等同于每次都要计算一个 page 能存放多少记录吗?那为什么是很难计算呢?
    andj4cn
        8
    andj4cn  
       2020-12-21 20:35:31 +08:00
    @zxCoder 确实,指向子 page 的 KV 里的 k 应该是不固定的。pairs_num_max = (page_size - header_size)/(pair_size),由于 pair_size 不固定而导致 page 可存储的 pairs 最大数量不固定。
    saberlong
        9
    saberlong  
       2020-12-21 21:45:48 +08:00 via Android
    页大小可以选择,决定了就固定了。所以要么 key 有长度限制,要么引入其它结构处理超大 key 和 value 。记得 mysql 是有 key 长限制的。最新的版本不清楚
    saberlong
        10
    saberlong  
       2020-12-21 21:48:30 +08:00 via Android
    我自己写的 b+树选择了不固定阶,key 有长度限制,value 不限。过大的 value 通过扩展页分割存储到多个页中。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   977 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 22:23 · PVG 06:23 · LAX 14:23 · JFK 17:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.