聊聊树状结构如何在数据库中存储
昨天有人在QQ小组问起,无限分层的树状结构,数据量比较大,在一万条以上,如何设计数据库的结构。其实这是个老生常谈的问题,一般的做法是有一个 pid字段,为了提高效率,还会有个FullPath字段。(一些人还设置一个层级字段,但我不知道这个字段有何作用),FullPath字段可以用 id-id-id….这种方式拼字符串存储,这样可以方便地用 like 语句进行查询某个节点及其子节点。
曾经看到过另外一种存储方式,利用了一般树结构可以转换二叉树的这一做法,用二叉树进行存储,在数据量大的情况下,存储读效率比上述的常见方案更优些,所以特写此文简单介绍一番。
下图说明了这种方案
如图所示,在每个节点上,有left ,right两个字段,我们看到,图上从根节点顺着子节点开始画一条线,每深入一层left加一,到底后,right=left+1,然后顺着节点回溯,right逐级加一,一直回到根节点。
如果要查询某个节点及其子节点,比如 fruit 节点 ,条件为 where left between 2 and 11
要查某个节点的full path ,比如 banana,条件为 where left<8 and right >9
如果要插入某个节点,比如red yellow直接插入一个节点,则update left =left+2 where left>=7 ,update right=right+2 where right>7,然后 新节点的left rigt分别是 7,8。 删除节点类似。
这种方式,因为id都是int型数据,加上索引后,读的效率较高。而fullPath字段的方案查询时候用的是字符串操作like,效率较低。
在内存中,如果要还原树状结构,即在每个节点上增加pid属性和children属性,则稍微麻烦些,可以如下操作:
- 按left between x and y order by left 取数据
- 顺序遍历数据,如果left=上一个Left+1,则是上一个节点的子节点,设置两个对象的父子关系,如果发生跳号,则是上一个节点的兄弟节点。
OK,大致的方案就介绍到这里
原文链接:http://www.cnblogs.com/honghuamin/archive/2011/07/24/2115635.html
【编辑推荐】
相关文章
- 从本体论开始说起——运营商关系图谱的构建及应用
- 如何成为一名数据科学家?
- 从未见过的堂兄杀了人,你的DNA是关键证据
- 20个安全可靠的免费数据源,各领域数据任你挑
- 20个安全可靠的免费数据源,各领域数据任你挑
- 阿里云李飞飞:All in Cloud时代,云原生数据库优势明显
- 基于Hadoop生态系统的一高性能数据存储格式CarbonData(性能篇)
- 大数据告诉你:10年漫威,到底有多少角色
- TigerGraph:实时图数据库助力金融风控升级
- Splunk利用Splunk Connected Experiences和Splunk Business Flow 扩大数据访问
- 大数据开发常见的9种数据分析手段
- 以免在景区看人,我爬了5W条全国景点门票数据...
- 【实战解析】基于HBase的大数据存储在京东的应用场景
- 数据科学家告诉你哪些计算机科学书籍是你应该看的
- Kafka作为大数据的核心技术,你了解多少?
- Spring Boot 整合 Redis 实现缓存操作
- 大数据学习必须掌握的五大核心技术有哪些?
- 基于Antlr在Apache Flink中实现监控规则DSL化的探索实践
- 甲骨文再次被Gartner评为分析型数据管理解决方案魔力象限领导者
- 爬取吴亦凡微博102118条转发数据,扒一扒流量的真假