多级目录树（森林）的三种数据库存储结构介绍-阿里云开发者社区

link之家

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

相关文章推荐

严肃的熊猫 · 技术讨论区-CSDN博客· 1 年前 ·

痴情的煎鸡蛋 · spring ...· 1 年前 ·

安静的领带 · 怎么修改进程名_百度知道· 1 年前 ·

斯文的豆浆 · 代理 - ...· 1 年前 ·

去年做过一个项目，需要每日对上千个Android内存泄漏（OOM）时core dump出的hprof文件进行分析，希望借助海量数据来快速定位内存泄漏的原因。最终的分析结果是一个类森林，因为时隔较远，只找到下面这个截图了。

点击打开折叠的项目，会看到该类的每个属性，类有多少个实例，占用的大小等等信息，树的深度可以达到10^2级别。重点是项目需要实时，每个hprof文件解析出来的节点达到5w+，千万级节点已经由mapreduce进行过一次汇聚计算才出库，在展示时，依然需要一次实时计算，当点击项目时，需要快速将该类下所有的子孙节点占用的字节大小累加到该节点，因此对森林要有很高的查询效率。

好的查询效率取决于好的存储机构，众所周知，多级目录树有如下三种存储方法，这里主要讲解这三种方式，并对其做了一些修改。这里使用同一个森林为模型（字母为节点名称，数字为节点权重）

这种方式最为开发人员熟知，每一个节点持有父节点的引用。为了更好的处理森林，抽象一个不存在的0节点，森林中所有树挂在改节点下，将森林转换为一颗树来处理。

改方法的SQL如下

1 CREATE TABLE node1 (
2   id INT AUTO_INCREMENT PRIMARY KEY ,
3   name VARCHAR(12) NOT NULL,
4   num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量、节点权重（可认为分类下产品数量）',
5   p_id INT NOT NULL DEFAULT 0 COMMENT '0表示根节点'
 此方法结构简单，更新也简单，但是在查询子孙节点时，效率低下，不能满足项目需求，因为这种方式过于简单，这里就不写该结构的查询更新删除SQL了。
进阶邻接列表
该方法仅仅需要在邻接列表的基础上，添加path_key（search_key）字段，该字段存储从根节点到节点的标识路径，这里依然抽象一个不存在的0节点。
该结构SQL表示如下：
1 CREATE TABLE node2 (
2   id INT AUTO_INCREMENT PRIMARY KEY ,
3   name VARCHAR(12) NOT NULL ,
4   num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量、节点权重（可认为分类下产品数量）',
5   p_id INT NOT NULL DEFAULT 0 COMMENT '0表示根节点',
6   search_key VARCHAR(128)  DEFAULT '' COMMENT '用来快速搜索子孙的key，存储根节点到该节点的路径',
7   level INT DEFAULT 0 COMMENT '层级'
重点在于search_key字段
插入测试数据
1 INSERT INTO node2(id,name, num, p_id,search_key) VALUES
2   (1,'A',10,0,'0-1'),
3   (2,'B',7,1,'0-1-2'),
4   (3,'C',3,1,'0-1-3'),
5   (4,'D',1,3,'0-1-3-4'),
6   (5,'E',2,3,'0-1-3-5'),
7   (6,'F',2,0,'0-6'),
8   (7,'G',2,6,'0-6-7');
查询森林中的根节点
1 # 查询森林的根节点
2 SELECT * FROM node2 WHERE p_id = 0 AND search_key LIKE '0-%' AND level = 0;
查询节点A的所有子孙节点
1 # SELECT * FROM node2 WHERE search_key LIKE '{A.search_key}%';
2 SELECT * FROM node2 WHERE search_key LIKE '0-1-%';
更新某个节点的权值，只需要一次select与一次update操作
1 # 例如，更新节点C的权重
2 UPDATE node2,( SELECT sum(num) AS sum FROM node2 WHERE search_key LIKE '0-1-3-%') rt SET num = rt.sum WHERE id=3;
有节点权重累加时，将所有父辈权重再加1，只需要将该节点的search_key以'-' 切分，得到的就是所有父辈的id（0除外）。例如，将节点D的权重+1，这里使用where locate，实际更好是先将search_key split之后使用where in查询
1 UPDATE node2,(SELECT search_key FROM node2 WHERE id = 4) rt SET num=num+1 WHERE locate(id,rt.search_key);
删除某个节点，比如删除B节点
假设删除节点子孙全部清理
1 DELETE FROM node2 WHERE search_key LIKE '0-1-2%';
假设子节点不清除 ，将子孙节点挂到父辈节点下，则需要更新儿子节点的search_key、p_id、level字段
1 # UPDATE node2, SET p_id = {B.p_id}
2 UPDATE node2 SET p_id = 1 AND search_key = concat('0-1-',id);
3 # 删除
4 DELETE FROM node2 WHERE id=2;
方式2仅仅添加了一个路径字段，使得查询变的简单，并且更新也容易，在节点深度有限的情况下，个人认为第二种方式是比较优的选择。
先序树结构
先序树即按照先序遍历的方式，给节点分配左右值，第一次到达该节点时，设置左值，第二次到达该节点，设置右值，每走一步，序号加1。这里以一段php代码来生成第一张图片中的森林的先序树结构
 1 <?php
 2 /**
 3  * Created by PhpStorm.
 4  * User: samlv
 5  * Date: 2017/2/23
 6  * Time: 16:44
 7  */
 9 $forest = array(
10     array(
11         'name'  =>  'A',
12         'num'   =>  10,
13         'childs' => array(
14             array(
15                 'name' => 'B',
16                 'num'   =>  7,
17                 'childs' => array()
18             ),
19             array(
20                 'name' => 'C',
21                 'num'   =>  3,
22                 'childs' => array(
23                     array(
24                         'name' => 'D',
25                         'num'   =>  1,
26                         'childs' => array()
27                     ),
28                     array(
29                         'name' => 'E',
30                         'num'   =>  2,
31                         'childs' => array()
32                     )
33                 )
34             )
35         )
36     ),
37     array(
38         'name' => 'F',
39         'num'   =>  2,
40         'childs' => array(
41             array(
42                 'name' => 'G',
43                 'num'   =>  2,
44                 'childs' => array()
45             )
46         )
47     )
48 );
50 function pre_order(& $forset,$level){
51     static $i = 1;
52     static $tree_id = 1;
53     foreach($forset as & $node){
54         $node['lft'] = $i ++ ;
55         if(!empty($node['childs'])){
56             pre_order($node['childs'],$level + 1);
57         }
58         $node['rgt'] = $i ++ ;
59         echo "{$node['lft']} | {$node['name']} | {$node['rgt']} \n";
60         //echo "insert into node3 (tree_id, name, num, lft, rgt, level) VALUE ($tree_id,'{$node['name']}',{$node['num']},{$node['lft']},{$node['rgt']},$level); \n";
61         if($node['lft'] === 1){
62             // 遍历新的树
63             $i = 1;
64             $tree_id ++;
65         }
66     }
67 }
69 pre_order($forest,1);
C:\xampp\php\php.exe D:\www\php-all\sp.php
2 | B | 3 
5 | D | 6 
7 | E | 8 
4 | C | 9 
1 | A | 10 
2 | G | 3 
1 | F | 4 
将结果解析成图片如下
我后续以这段代码生成了SQL insert代码。用来存储该森林的SQL如下
 1 CREATE TABLE node3 (
 2   id INT AUTO_INCREMENT PRIMARY KEY ,
 3   tree_id INT NOT NULL COMMENT '为保证对某一棵的操作不影响森林中的其他书',
 4   name VARCHAR(12) NOT NULL ,
 5   num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量、节点权重（可认为分类下产品数量）',
 6   lft INT NOT NULL ,
 7   rgt INT NOT NULL ,
 8   level INT DEFAULT 0
 9 );
10 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'B',7,2,3,2);
11 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'D',1,5,6,3);
12 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'E',2,7,8,3);
13 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'C',3,4,9,2);
14 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'A',10,1,10,1);
15 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (2,'G',2,2,3,2);
16 insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (2,'F',2,1,4,1);
这里加入了一个tree_id字段，用来保证对一棵树内的更新操作，不会影响到别的树，有利于提高效率。
对该结构的操作可以非常复杂，这里说两种基本的单元操作。
append操作，待加入节点不带子节点
remove操作，待删除节点没有子节点
首先来看append操作，我想在节点C下添加一个M节点，如图
仔细看可以发现，在已有一个节点下append一个节点M的话，M的左右值应该连续的，按照先序遍历的顺序，只需要将走在其后的节点的左右值分别+2，并且M节点的父节点的右值必然也要+2。下面以一个mysql function来实现append过程
 1 DROP FUNCTION IF EXISTS append_node;
 2 CREATE FUNCTION append_node(param_name VARCHAR(12), param_num INT, param_p_id INT, param_tree_id INT)
 3   returns INT
 4   BEGIN
 5     DECLARE p_lft INT;
 6     DECLARE p_rgt INT;
 7     DECLARE p_level INT;
 8     DECLARE ret INT;
10     SELECT lft,rgt,level INTO p_lft,p_rgt,p_level FROM node3 WHERE tree_id = param_tree_id AND id=param_p_id ;
11     # 比前一个节点左值大的需要加2
12     UPDATE node3 SET lft = lft + 2 WHERE tree_id = param_tree_id AND lft > p_lft;
13     # 按照先序遍历规则，在一个节点M下添加节点之后，节点M的右值必然也要加2
14     UPDATE node3 SET rgt = rgt + 2 WHERE tree_id = param_tree_id AND rgt >= p_rgt;
15     INSERT INTO node3 (tree_id,name, num, lft, rgt, level)
16       VALUE (param_tree_id,param_name,param_num,p_lft + 1,p_rgt + 1,p_level + 1);
17     SELECT LAST_INSERT_ID() INTO ret;
18     RETURN ret;
19   END;
21 # 在节点C下添加节点M，已知节点C的id为4，tree_id为1。
22 select append_node('M', 7, 4, 1);
除了append操作之外，还可以有insert操作，如下图
其实insert操作可以看做是append 与 delete或者update结合的操作，不一定要一步到位，可以由单元操作来组成。
至于remove操作，则恰好是append操作的反向操作，需要将被删除节点后面的节点的左右值-2。最后进行delete操作。另外，删除要分两种情况，就是子孙丢弃与子孙不丢弃。
                霜皮剥落紫龙鳞，下里巴人再谈数据库SQL优化，索引(一级/二级/聚簇/非聚簇)原理
            举凡后端面试，面试官不言数据库则已，言则必称SQL优化，说起SQL优化，网络上各种“指南”和“圣经”难以枚举，不一而足，仿佛SQL优化已然是妇孺皆知的理论常识，然后根据多数无知（Pluralistic ignorance）理论，人们印象里觉得多数人会怎么想怎么做，但这种印象往往是不准确的。那SQL优化到底应该怎么做？本次让我们褪去SQL华丽的躯壳，以最浅显，最粗俗，最下里巴人的方式讲解一下SQL优化的前因后果，前世今生。
                程序员必备的数据库知识：数据存储结构
            本文介绍了五种常见数据存储结构，另外还有图、表格、链式、R-TREE等数据结构并未涉及，当然本文也只是对数据库存储结构的知识抛砖引玉，有兴趣的同学可以对每一种数据存储结构做更详细和深入的学习。司马辽太杰是 NineData 工程师。NineData 向企业和个人提供高效、安全的数据库SQL开发、数据库备份、数据复制/迁移/集成、数据对比等功能，是一个SaaS服务开箱即用，可以快速提升企业SQL开发效率，保障企业数据安全。NineData 官网地址：https://ninedata.cloud
                【数据库系列】存储引擎（二）B树概述
            注：在本文中“结点”和“节点”同义，在B树部分，“节点”和“页”同义。 背景知识 很多数据库都是基于B树 传统树的特点回顾 由数据结构与算法的知识可知，BST（二叉搜索树）的左子树的值<根值<右子树的值。
                浅析数据库算法与数据结构（三） B树
            上一期我们谈到了数据库实现快速查找的所使用的的HASH算法，能够实现O(1)复杂的快速查找，HASH算法虽然好，但是有一个致命的缺点，就是HASH函数算出的散列值，通常是随机分布，没有顺序性。这时候我们就需要使用到B树
                数据库必知词汇：平衡多路查找树B-Tree
            B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。B-Tree中的B代表平衡（balance），而不是二叉（binary），因为B-Tree树是从最早的平衡二叉树演化而来的。这个数据结构一般用于数据库的索引，综合效率较高。