去年做过一个项目，需要每日对上千个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表示根节点'
6 );
此方法结构简单，更新也简单，但是在查询子孙节点时，效率低下，不能满足项目需求，因为这种方式过于简单，这里就不写该结构的查询更新删除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 '层级'
8 );
重点在于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 */
8
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 );
49
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 }
68
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;
9
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;
20
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操作。另外，删除要分两种情况，就是子孙丢弃与子孙不丢弃。