案情综述
树形结构在开发过程中很常见，菜单树、文件目录树、组织架构数、树形控件……等等，由于树形结构的数据结构比较特殊，不适于直接存储，特别是存储在关系型数据库中。所以通常数据库中对树形结构的存储都进行了某种转换，最常见的方式就是以节点<->父节点对的方式进行描述和存储，这种存储的优点是，结构简单，层次描述清晰，特别是对于层级不确定的情况，弹性很大，理论上可以存储任意深度和广度的树，缺点是在初始化树的时候需要进行数据转换，在节点数大的情况下，转换效率就成了首要问题。最常见的转换方式——也是针对节点<->父节点对的存储方式设计的——就是递归转换了。

递归算法很常见，并且通常是代码简洁和高效率的代表，但是在上述树形结构的实践过程中，很容易发生性能问题。

现场重建
下面的叙述，是基于工程实践中实际发生的一个低性能案例及其优化过程改编的，测试的平台基于一台笔记本，i5 M560双核CPU，主频2.67G，内存4G，运行Windows 7 x64操作系统，开发环境是Visual Studio 2010，.Net Framework 4.0。

实际案例中，树形结构是WinForm的TreeView控件，它的TreeNode具有Nodes属性，Nodes属性是一个TreeNode的列表，以此实现树形结构的组装与呈现。为了简化程序编译，我们用一个TreeNodeDemo对象来代表这个结构，只实现最基本的数据结构：

    public class TreeNodeDemo
    {
        private List<TreeNodeDemo> _nodes;
        public List<TreeNodeDemo> Nodes
        {
            get
            {
                return _nodes;
            }
        }

        public TreeNodeDemo()
        {
            _nodes = new List<TreeNodeDemo>();
        }

        public string Name
        {
            get;
            set;
        }

        public object Tag
        {
            get;
            set;
        }
    }

案例中存储节点数据的数据表和模型对象也比较复杂，这里简化成一个NodeData对象，除了必须的ID<->ParentID属性对，只有一个Name属性：

    public class NodeData
    {
        public int ID
        {
            get;
            set;
        }

        public int ParentID
        {
            get;
            set;
        }

        public string Name
        {
            get;
            set;
        }
        public NodeData(int id, int parentID, string name)
        {
            ID = id;
            ParentID = parentID;
            Name = name;
        }
    }

节点的ID、ParentID不能为空，每个节点的ParentId必须指向某个已存在的NodeData的ID属性，ParentID = 0的节点是第一级节点（位于根节点下），不存在ID = 0的节点。

先建一个初始化递归存储对象列表的方法，用比较常规的结构，名为InitNormalNodeDatas，把性能指标放大一些，放10,000个节点，大致平均地分布在7级目录中。用的方法比较笨，能把数据填进去就行了：

        public static List<NodeData> InitNormalNodeDatas()
        {
            List<NodeData> result = new List<NodeData>(10000);
            //先初始化10个一级节点（id=1-10）；
            int n=0;
            for (int i = 0; i < 10; i++)
                result.Add(new NodeData(++n, 0, "ID = " + n.ToString() + "; ParentID = 0"));
           
            //初始化90个二级节点（id=11-100）；节点数10+90=100
            for (int i = 1; i < 10; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));

            //初始化800个三级节点（id=101-800）；节点数100+800=900
            for (int i = 11; i < 91; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));

            //初始化5000个四级节点（id=901-5900）；节点数5000+900=5900
            for (int i = 101; i < 601; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));

            //初始化3000个五级节点（id=5901-8900）；节点数5900+3000=8900
            for (int i = 901; i < 1201; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));

            //初始化1000个六级节点（id=8901-9900）；节点数8900+1000=9900
            for (int i = 5901; i < 6001; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));

            //初始化100个七级节点（id=9901-10000）；节点数9900+100=10000
            for (int i = 8901; i < 8911; i++)
                for (int j = 0; j < 10; j++)
                    result.Add(new NodeData(++n, i, "ID = " + n.ToString() + "; ParentID = " + i.ToString()));
            return result;
        }

BuildTreeOld是原来的构建树方法的入口，ANodeOld是建树方法的核心，是一个递归方法：

        public static TreeNodeDemo BuildTreeOld(List<NodeData> nodeDatas)
        {
            TreeNodeDemo result = new TreeNodeDemo();
            if (nodeDatas != null && nodeDatas.Count > 0)
            {
                var rows = from i in nodeDatas
                           where ( i.ParentID==0)
                           select i;
                if (rows != null && rows.Count() > 0)
                {
                    foreach (NodeData row in rows)
                    {
                        TreeNodeDemo node = new TreeNodeDemo();
                        node.Name = row.Name;
                        node.Tag = row;
                        result.Nodes.Add(node);
                        ANodeOld(nodeDatas, node, row.ID);
                    }
                }
            }
            return result;
        }

        public static void ANodeOld(List<NodeData> nodeDatas, TreeNodeDemo node, int parentID)
        {
            try
            {
                if (nodeDatas != null && nodeDatas.Count > 0)
                {
                    List<NodeData> rows = (from i in nodeDatas
                                           where i.ParentID == parentID
                                           select i).ToList();
                    if (rows != null && rows.Count() > 0)
                    {
                        foreach (NodeData row in rows)
                        {
                            TreeNodeDemo childNode = new TreeNodeDemo();
                            childNode.Name = row.Name;
                            childNode.Tag = row;
                            node.Nodes.Add(childNode);
                            ANodeOld(nodeDatas, childNode, row.ID);
                        }
                    }
                    else
                    {
                        return;
                    }
                }
            }
            catch
            {
            }
        }

首先看看代码的大致结构：ANodeOld中使用LINQ对NodeData列表进行筛选，找出所有ParentID等于当前节点ID的所有节点，也就是子节点，然后再对这些节点进行遍历并递归。
这个算法从功能上看去没什么问题，逻辑清晰、代码简洁，但是执行效率呢？完成这10,000个节点的组装花了大约3,600毫秒。实际案例中，打开一个窗口的过程里，需要用这样的算法初始化若干TreeView控件，导致窗口打开缓慢，这也是决定进行优化的起因。

案情分析
仔细分析代码，问题应当处在LINQ筛选上，LINQ的写法看上去和SQL很相似，所以程序员很自然的认为这种查找应当会和数据库一样有效率，但事实上，这只是LINQ语法带来的假象。

首先，LINQ查询在执行时，执行效率取决于被查找集合的实现方式，对于本例中来说，取决于List类的查找效率，这与数据库有些差别，数据库中查询字段如果没有索引，理论上两者的执行效率差别不大，但数据库可以通过建立字段索引极大地提高查询效率，而在应用程序代码中，受到开发环境、代码工程上下文的限制，对集合实现方式的可选择余地不大。在Framework的具体实现中，HashSet和Dictionary有着与索引类似的高效查找算法，但灵活性与数据表相比，仍有显著差距。

其次，本例中，LINQ查询的查询条件是集合项目中对象的属性（i.ParentID == parentID），这必然导致LINQ需要遍历整个集合项目，查找每个集合项的相关属性值，这与数据库中对字段应用表达式引发索引失效的情况类似。这个过程必须获取对象指针、再执行属性的get方法或获取字段（Field）的值、最后才执行比较操作。这种情况下，即便使用HashSet或Dictionary，也无法得到任何好处，因为它们只能对存储的对象或Key进行查找优化，而不是对象的属性。

真相大白
按照上述原理，每次递归调用，都将导致遍历List<NodeData>，也就是说，完成整棵树的构建，需要在一个10,000项的集合中执行10,000次查找，执行效率可想而知。

知道了问题所在，接下来就是如何解决它。首先想到的就是怎么用最优化的集合实现来存储这些节点，以提高查找效率，上面说了，最高效的集合实现应当是HashSet和Dictionry，根据文档，这两种集合对于给定对象或Key的查找复杂度为O(1)，相当高了。

接下来的问题是，要想提高效率，执行比较操作的属性，必须直接存储在HashSet中或Dictionary的Key中，这样才能发挥两者的效率。HashSet只能存储对象本身，所以不适合，看来只能用Dictionary了，它可以以Key, Value的方式存储两个对象，并以Key作为索引查找条件，比较接近我们的需求。

Dictionary要求对象或Key不能重复，而本例中，执行比较的是ParentID，但ParentID恰恰是会重复的（一个节点下会有多个子节点），需要做某种形式的再次转换才行。考虑到在实际的树状结构中，相同父节点的节点总是会编排到同一个列表中，例如TreeNodeDemo.Nodes，换句话说，可以按ParentID进行分组，分组的结果，各组节点的ParentID必然是不重复的。因此可以设计如下结构进行：
Dictionary<int, List<TreeNodeDemo>>，Dictionary的Key是int，存放分组后的ParentID；Value是相同ParentID的子节点集合List<TreeNodeDemo>。这样分组后，新的集合中项目的数量等于整棵树中存在子节点的节点数量+1（加1是因为第一级节点的父节点并不在集合中，但第一级节点会被归在一起）。按前面的初始化方法，应当只有1000个这样的节点。这样构建树时，只需要自上而下的依次查找ParentID等于本节点ID的节点集合并添加即可，需要经历的查找次数就少多了；另外，这种结构也可以充分发挥Dictionary的查找性能优势。当然，这个方法也有一些成本——必须增加额外的过程，把List<NodeData>转换成Dictionary<int, List<TreeNodeDemo>>，但是只要方法得当，收益仍然是可观的。
转换方法如下：

        private static Dictionary<int, List<NodeData>> Convert(List<NodeData> nodeDatas)
        {
            Dictionary<int, List<NodeData>> result = new Dictionary<int, List<NodeData>>();
            foreach (NodeData nodeData in nodeDatas)
            {
                List<NodeData> subNodes = null;
                if (!result.TryGetValue(nodeData.ParentID, out subNodes))
                {
                    subNodes = new List<NodeData>();
                    result.Add(nodeData.ParentID, subNodes);
                }
                subNodes.Add(nodeData);
            }
            return result;
        }

修改后的建树代码如下：

        public static TreeNodeDemo BuildTreeNew(List<NodeData> nodeDatas)
        {
            TreeNodeDemo result = new TreeNodeDemo();
            if (nodeDatas != null && nodeDatas.Count > 0)
            {
                Dictionary<int, List<NodeData>> newDatas = Convert(nodeDatas);
                List<NodeData> subNodes = null;
                if (newDatas.TryGetValue(0, out subNodes))
                {
                    foreach (NodeData subNode in subNodes)
                    {
                        TreeNodeDemo node = new TreeNodeDemo();
                        node.Tag = subNode;
                        node.Name = subNode.Name;
                        ANodeNew(newDatas, node, subNode.ID);
                        result.Nodes.Add(node);
                    }
                }
            }
            return result;
        }

        public static void ANodeNew(Dictionary<int, List<NodeData>> newDatas, TreeNodeDemo parentNode, int parentID)
        {
            if (newDatas != null && newDatas.Count > 0)
            {
                List<NodeData> subNodes = null;
                if (newDatas.TryGetValue(parentID, out subNodes))
                {
                    foreach (NodeData subNode in subNodes)
                    {
                        TreeNodeDemo rootNode = new TreeNodeDemo();
                        rootNode.Tag = subNode;
                        rootNode.Name = subNode.Name;
                        ANodeNew(newDatas, rootNode, subNode.ID);
                        parentNode.Nodes.Add(rootNode);
                    }
                }
            }
        }

优化后的组装时间大约10毫秒，快了360倍，差距十分惊人。实际情况中，组装效率与对象的复杂度有关，对象的实例化和初始化都是要花时间的，所以差距不一定有这么明显。在我们的实际案例中，优化前后的消耗时间的差别大约有200倍，这也足够惊人了，以至于我们反复检查了好几次程序并逐步跟踪代码，怀疑是不是哪些步骤没执行。

深入探究：
如果有一个极端的树状结构，每一层只有一个节点，每个节点只有一个子节点，也就说，这棵树有10,000级，还真够极端的-_-!这种情况下，两种方法的对比如何呢？
还是先初始化数据列表，新建一个方法，名为InitSerializeNodeDatas：

        public static List<NodeData> InitSerializeNodeDatas()
        {
            List<NodeData> result = new List<NodeData>(10000);
            for (int i = 0; i < 10000; i++)
                result.Add(new NodeData(i + 1, i, "ID = " + (i + 1).ToString() + "; ParentID = " + i.ToString()));
            return result;
        }

再考虑一下优化前后两种结构在数量上的差别，转换前的集合，有10,000个对象；转换后的集合项目数等存在子节点的节点数量，在这里，除了最后一级节点，每个节点都有子节点，所以转换后仍然有10,000个项目。这时候考验的就是新旧两种结构查找算法的效率啦。

测试过程却发生了问题，这个程序一运行就报出错误：StackOverflow，栈溢出。很明显，这是由于递归深度太大造成的，10,000级哦，不溢出才怪。找了半天，C#好像没有编译器选项允许直接指定栈大小。只能用VC++带的工具Editbin来修改编译后可执行文件的头信息，语法如下：editbin /STACK:104857600 BuildTree.exe，这是把程序的栈大小改成了100M，这下才可以正常执行。

测试结果如下：
优化前 3,600ms，优化后36ms。
即便在最恶劣的条件下，新的算法仍然有着绝对优势。这下充分体现出Dictionary的查找效率了吧。

下面再试试另一个极端吧，有左就有右，这回只有一个一级节点，剩下的其他节点都是它的直接子节点，结构只有两层，一个大平板！初始化数据列的方法名为InitFlatNodeDatas：

        public static List<NodeData> InitFlatNodeDatas()
        {
            List<NodeData> result = new List<NodeData>(10000);
            result.Add(new NodeData(1, 0, "ID = 1; ParentID = 0"));
            for (int i = 1; i < 10000; i++)
                result.Add(new NodeData(i + 1, 1, "ID = " + (i + 1).ToString() + "; ParentID = 1"));
            return result;
        }

这次，转换后的集合，只包含2项，肯定轻松获胜。

测试结果如下：
优化前 3,600ms，优化后9ms左右，与常规方法初始化的数据相比，优化后方法的差距不太明显，原因在于Dictionary的查找算法对于集合中的数据量不敏感，换句话说，Dictionary里有10个项目和1,000,000个项目时的查找所需时间相差不多。
但与上一个极端情况的差别还是比较大的，原因在于：查找的次数，这里只查找了2次，而上面则执行了10,000次。

有兴趣的话，可以把转换消耗的时间计算出来，这样剩下的就完全是集合查找的时间了，这可以使对比不同集合实现方式的查找效率可以更加精确一些。

另外，按照前面的描述，新旧两种方法，在节点数少时的差别应该不太明显，而随着节点数增加，差距应当是呈几何增长的，这个应当也可以进行验证。

结案陈词：
这个案例可以说明两个问题：
1. LINQ很强大，但是不甚理解的去应用，可能会带来性能损耗。
2. 集合类型的不同具体实现，在查找效率上的差别显著，在实际应用比，必须仔细斟酌应用场景，选用恰当的类型。

这类性能问题在开发阶段、普通测试阶段、甚至是上线之初可能都暴露不出来，往往等到系统部署一段时间后，生产环境的数据量累积到一定程度，才可能感觉性能有问题。而实际环境中，可能导致性能问题的原因存在于系统运行环境的各个环节，这个时候再去找原因，可能就如大海捞针了。要避免这类问题，除了要时刻绷紧效率这根弦之外，前面提到的2个问题也必须引起注意。

当然，这个案例的优化方案不止一个，记录这个案例只是为了对比不同集合类型查找效率的差异，为今后的开发提供借鉴。