文章标签 ‘前序遍历’

Django mptt介绍以及使用

Django mptt是个Django第三方组件,目标是使Django项目能在数据库中存储层级数据(树形数据)。它主要实现了修改过的前序遍历算法,如果你对原理还不是很了解,可以看我的这篇文章。当然,使用mptt时,原理是可以不用了解的,因为具体的实现细节都已经隐藏。不过,如果项目不是使用的Django,可以参考具体的实现原理。

在整篇文章中,我们将会拿《在数据库中存储层级结构》中的例子作为本文的例子。我们打算在数据库中存储这张图中的数据:

树

在介绍mptt之前,如果你的需求仅仅是像这样显示以上数据:

  • Food
    • Fruit
      • Red
        • Cherry
      • Yellow
        • Banana
    • Meat
      • Beef
      • Pork
  • mptt就显得大材小用了,因为Django已经有内置模板过滤器来完成这个工作:unordered_list(官方文档)。如果你的需求不只这么简单,那就跳过这一段。不过这里还是要讲解一下unordered_list的做法。我们就来实现以上的结果。

    在数据库中存储层级结构

    本文参考自这篇文章。文章是2003年的,但是现在来看仍然有着实际意义。

    层级结构,也叫树形结构。在实际应用中,你经常需要保存层级结构到数据库中。比如说:你的网站上的目录。不过,除非使用类XML的数据库,通用的关系数据库很难做到这点。

    对于树形数据的存储有很多种方案。主要的方法有两种:邻接表模型,以及修改过的前序遍历算法。本文将会讨论这两种方法的实现。这里的例子沿用参考文章中的例子,原文使用的PHP,这里将会用Java替代。(本例使用Mysql数据库,Java如何连接Mysql,见备注一。)文中使用虚拟的在线食品商店作例子。这个食品商店通过类别、颜色以及种类来来组织它的食品。如图所示:

    例子

    关于作者

    残阳似血(@秦续业),程序猿一枚,把梦想揣进口袋的挨踢工作者。现加入阿里云,研究僧毕业于上海交通大学软件学院ADC实验室。熟悉分布式数据分析(DataFrame并行化框架)、基于图模型的分布式数据库和并行计算、Dpark/Spark以及Python web开发(Django、tornado)等。

    博客分类

    点击排行

    标签云

    扫描访问

    主题

    残阳似血的微博