左右值
左右值
红猪-侠 发表于5年前
左右值
  • 发表于 5年前
  • 阅读 173
  • 收藏 1
  • 点赞 0
  • 评论 0
摘要: 左右值的核心就是牺牲了写的性能来换取读取的性能,在你的开发的应用遇到此类问题的时(读压力 > 写压力),尝试使用这种数据结构来提高你的程序的性能吧。

左右值树,即预排序遍历树(Modified Preorder Tree traversal),用于在数据库中存储层级数据结构,构建过程如下:

原始数据库设计:

CREATE TABLE `comment1` (

  `id` int(10) unsigned NOT NULL,

  `lvl` int(10) unsigned NOT NULL,

  `lft` int(10) unsigned NOT NULL,

  `rgt` int(10) unsigned NOT NULL,

  PRIMARY KEY (`id`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8;

左右值树的一些性质:

  • 计算节点node除自己外的子节点总数,( node(rgt) - node(lft) + 1 ) / 2 - 1;
  • 叶子节点属性:node(rgt) - node(lft) = 1;
  • 查询节点node下所有子节点:SELECT lvl,lft,rgt FROM comment WHERE lft>node(lft) AND rgt<node(rgt) ORDER BY lft ASC;
  • 查询节点A,节点B之间的所有节点:SELECT * FROM comment WHERE lft>=A(lft) AND lft<=B(lft) AND rgt<=A(rgt) AND rgt>=B(rgt) ORDER BY lft ASC;

在满足根节点除外的所有节点有且只有一个儿子节点的情况下,还有如下性质:

  • 已知任意节点node,可以计算得到该节点所在直线分支的节点总数:( node(rgt) - node(lft) + 1 ) / 2 + node(lvl) - 1;
标签: MPTT
共有 人打赏支持
红猪-侠
粉丝 0
博文 1
码字总数 325
作品 1
×
红猪-侠
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: