简单的带索引树构建

2017-06-12

综述

日常开发中常会遇到有相互隶属关系的同种数据，例如用户权限，网站地图，文档目录，以及一些动态的分类方式等，甚至是pypi上的项目引用关系。此时相信大家都明白，应该使用的数据结构是树。

大家都知道使用树，那如何用得好，不至于走岔迷失呢？在我看来，重点一是在于方便寻址，根据业务需要，在创建树的同时创建好一个或多个适用的索引表；二是将树可视化、形象化，通过添加节点特征，规范变量名，或者建立可靠的序列化输出机制，从而便于程序判断和debug。这两点非常有助于程序猿快速建立对这个树的直观映像，并提升代码的表达能力。

我相信，一个好的工程师应该拥有的素质，不是在复杂的数据结构中绕来绕去而不晕的能力，而是将一个看似复杂的数据结构快速梳理出线索，使其简单可靠的能力。而运用好之前提到的两点，就如同在几何题中做出了关键辅助线。

实践一文档树

产品中有帮助系统，帮助文档的目录是一个简单的三层结构：产品，子目录，页面。

早年的目录结构是页面存在数据库中，子目录和产品的关系以字典结构直接写在代码中。后来又重构成了目录结构都以节点方式放在数据库，在代码中创建为树。
数据样例如下：

{"id": 0, "name": "some help menu"}
{"id": 1, "name": "yet a menu", "root": 0}
{"id": 2, "name": "menu x", "root": 1}
{"id": 3, "name": "another", "root": 0}
{"id": 4, "name": "some other product"}

但是这里有个问题，这段代码中每当需要使用到某一确定id的帮助文档时，总是在树中进行深度优先查找，嵌套多层循环。反向查找其父级内容创建面包屑时，又是在节点列表中不断循环查找其id和当前节点父级id相同的节点，直到父级id属性为空。
这种自找麻烦的情况在搜索帮助文档内容时达到峰值，页面需要一个新的缩小的树状结构用于展示搜索结果的分布情况并计数，代码中进行的判断和循环多达6次嵌套。请注意，也许有算法课教树的搜索是深度优先和广度优先等等。但是，我们使用时千万不要轻易在树中搜索。我们需要的是捷径。

我们来看看我们对此数据结构的需求是什么样的：

页面上有个树形的帮助文档索引需要展示
当显示某个确定的帮助文档时，需要展示面包屑导航栏
对帮助进行搜索，展示时树中仅显示被命中的项目，并对每个分类被搜索到的项目计数

为了能实现这个简单的需求，我们需要对这个树添加一个索引。

首先，我们定义一个类，这个类的功能很简单，就是生成目录树，实例化完毕后，其tree属性就是一个描述树图的大字典，id_index属性则是一个id索引，另外，还在数据内部添加了一点标记。如下：

self.tree = {
    'id_0': {
        ...   # root content
        menu_level: 0,
        children: {
            'menu_id': { ..., children: {...}}
            'menu_id': { ..., children: {...}}
            }
        }
    }
self.id_index = {
    'id_0': root_data,  # 即self.tree中root_
    'id_1': data_1,  # 即self.tree中children下的dict对象
    'id_2': data_2,
    'id_3': data_3,
    ...,
    }

这里用到了python中对可变对象的引用或其他语言中的指针，这样的数据结构有个好处，就是可以根据id快速定位到某个帮助页面，同时根据获得的这个字典对象在树形图中快速寻找其下级目录，或者根据其root属性再次在index中定位其父级页面。

生成代码大致如下：

# 生成一个简单的树

class HelpMenuTree(object):

    def __init__(self, node_list):
        self.tree, self.id_index = self.__build(node_list)

    def __build(self, node_list):
        # 生成树的同时将每个节点放入到id_index中

此结构较为简易，没有在子节点的数据中留下指向父级的指针，仅保留了父级id，故可直接利用self.id_index查找父级，快速生成面包屑。

从这个例子，我们可以显而易见的发现索引的好处。同理可见于实践二。

实践二权限树

我们产品后台的Django系统中虽然已利用原生权限系统，历来权限书写极为混乱，一个模块可能有几十个权限散落于各个页面，书写的权限名称也有随意性，与具体功能无法一一对应，亟待解决。经历某些事件，痛定思痛之后，决定重新创建一套权限系统。

首先，研究Django系统的特性之后，决定直接利用框架URL路由系统来作为权限系统的根基。先整理URL命名以吻合整个后台的页面层级，然后以路由树直接复刻出整个网站地图，从而可以通过这个树直观感受整个后台权限结构。我们在此创建出两个类，节点类及网络类，用以控制这整个树结构。创建树的逻辑很简单：

class RouterNode(object):

    def __init__(self, **kwargs):
        self.url = ...
        self.name = ...
        self.is_leaf = True/False
        self.perms = {
            'get': [],
            'post': [],
            'put': [],
            'patch': []
        }
        self.parent = ...
        self.children = [...]


class NodeNetwork(object):

    def __init__(self, router_data):
        self.root_node = RouterNode('', root_node=True)
        self.__url_map = self.__build_tree_by_routers(router_data)
        self.__name_map = {
            node.name: node for node in self.__path_tree.values()
        }

    def __build_tree_by_routers(self, router_data):
        """
        根据url的分解目录等级，创建以self.root_node为根, 每个独立权限为叶子节点的树。
        同时将url, name 分别建立索引
        """

    def get_node_by_url(self, url):
        return self.__url_map.get(url)

    def get_node_by_name(self, name):
        return self.__name_map.get(name)

    def get_all_sub_node(self, url):
        """
        根据非叶子节点获取所有叶子节点的值
        """

至此，我们同时可以在前端也用一个简单的递归把树创建到前端页面上，给予每个节点一个展开收起按钮，一个复选框，后台的权限管理是否立刻就清晰明了了呢~
同时，由于在树中添加了索引，根据url及权限名称寻找权限也是O(1)的操作，极为快速简洁，虽然是树的结构，一点也不影响操作速度。

综上

本文建议对业务中常见的对象间有较多关联关系的情况，直接在代码逻辑中将数据构建为多维度的关系映射，可同时构建为树，图，哈希map，队列等多重结构。可以同时利用多种数据结构的优势灵活编码，提高效率，且可令代码清晰明了。

#树 #思维碎片

简单的带索引树构建

综述

实践一 文档树

实践二 权限树

综上

实践一文档树

实践二权限树