精华内容
下载资源
问答
  • 最初是 MySQL 官方网站上看到这篇名为 Managing Hierarchical Data in MySQL 文章(MySQL 随 Sun 一起被 Oracle 收购后,现在只能通过 archive.org 找回了),原作者 Mike Hillyer 个人网站上再次看到。...

    最初是在 MySQL 官方网站上看到这篇名为 Managing Hierarchical Data in MySQL 的文章(MySQL 随 Sun 一起被 Oracle 收购后,现在只能通过 archive.org 找回了),在原作者 Mike Hillyer 的个人网站上再次看到。

    这份笔记在 MySQL 5.7 环境中对原文进行了复盘,调整了例子,同时SQL 语句根据个人习惯和 MySQL 版本的变化相比原文略有调整。

    概述

    我们知道,关系数据库的表更适合扁平的列表,而不是像 XML 那样可以直管的保存具有父子关系的层次结构数据。

    首先定义一下我们讨论的层次结构,是这样的一组数据,每个条目只能有一个父条目,可以有零个或多个子条目(唯一的例外是根条目,它没有父条目)。许多依赖数据库的应用都会遇到层次结构的数据,例如论坛或邮件列表的线索、企业的组织结构图、内容管理系统或商城的分类目录等等。我们如下数据作为示例:

    221c664395190b544eae8f4d34bda144.png

    数据来源于维基百科的这个页面,为什么挑了这几个条目,以及是否准确合理在这里就不深究了。

    Mike Hillyer 考虑了两种不同的模型——邻接表(Adjacency List)和嵌套集(Nested Set)来实现这个层次结构。

    邻接表(Adjacency List)模型

    我们可以很直观的使用下面的方式来保存如图所示的结构。

    创建名为 distributions 的表:

    CREATE TABLE distributions (

    id INT NOT NULL AUTO_INCREMENT,

    name VARCHAR(32) NOT NULL,

    parent INT NULL DEFAULT NULL,

    PRIMARY KEY (id)

    )

    ENGINE = InnoDB

    DEFAULT CHARACTER SET = utf8;

    插入数据:

    INSERT INTO distributions VALUES

    (1, 'Linux', NULL),

    (2, 'Debian', 1),

    (3, 'Knoppix', 2),

    (4, 'Ubuntu', 2),

    (5, 'Gentoo', 1),

    (6, 'Red Hat', 1),

    (7, 'Fedora Core', 6),

    (8, 'RHEL', 6),

    (9, 'CentOS', 8),

    (10, 'Oracle Linux', 8);

    执行:

    SELECT * FROM distributions;

    可以看到表中的数据形如:

    +----+--------------+--------+

    | id | name | parent |

    +----+--------------+--------+

    | 1 | Linux | NULL |

    | 2 | Debian | 1 |

    | 3 | Knoppix | 2 |

    | 4 | Ubuntu | 2 |

    | 5 | Gentoo | 1 |

    | 6 | Red Hat | 1 |

    | 7 | Fedora Core | 6 |

    | 8 | RHEL | 6 |

    | 9 | CentOS | 8 |

    | 10 | Oracle Linux | 8 |

    +----+--------------+--------+

    使用链接表模型,表中的每一条记录都包含一个指向其上层记录的指针。顶层记录(这个例子中是 Linux)的这个字段的值为 NULL。邻接表的优势是相当直观和简单,我们一眼就能看出 CentOS 衍生自 RHEL,后者又是从 Red Hat 发展而来的。虽然客户端程序可能处理起来相当简单,但是使用纯 SQL 处理邻接表则会遇到一些麻烦。

    获取整棵树以及单个节点的完整路径

    第一个处理层次结构常见的任务是显示整个层次结构,通常包含一定的缩进。使用纯 SQL 处理时通常需要借助所谓的 self-join 技巧:

    SELECT

    t1.name AS level1,

    t2.name as level2,

    t3.name as level3,

    t4.name as level4

    FROM

    distributions AS t1

    LEFT JOIN distributions AS t2

    ON t2.parent = t1.id

    LEFT JOIN distributions AS t3

    ON t3.parent = t2.id

    LEFT JOIN distributions AS t4

    ON t4.parent = t3.id

    WHERE t1.name = 'Linux';

    结果如下:

    +--------+---------+-------------+--------------+

    | level1 | level2 | level3 | level4 |

    +--------+---------+-------------+--------------+

    | Linux | Red Hat | RHEL | CentOS |

    | Linux | Red Hat | RHEL | Oracle Linux |

    | Linux | Debian | Knoppix | NULL |

    | Linux | Debian | Ubuntu | NULL |

    | Linux | Red Hat | Fedora Core | NULL |

    | Linux | Gentoo | NULL | NULL |

    +--------+---------+-------------+--------------+

    可以看到,实际上客户端代码拿到这个结果也不容易处理。对比原文,我们发现返回结果的顺序也是不确定的。在实践中没有什么参考意义。不过可以通过增加一个 WHERE 条件,获取一个节点的完整路径:

    SELECT

    t1.name AS level1,

    t2.name as level2,

    t3.name as level3,

    t4.name as level4

    FROM

    distributions AS t1

    LEFT JOIN distributions AS t2

    ON t2.parent = t1.id

    LEFT JOIN distributions AS t3

    ON t3.parent = t2.id

    LEFT JOIN distributions AS t4

    ON t4.parent = t3.id

    WHERE

    t1.name = 'Linux'

    AND t4.name = 'CentOS';

    结果如下:

    +--------+---------+--------+--------+

    | level1 | level2 | level3 | level4 |

    +--------+---------+--------+--------+

    | Linux | Red Hat | RHEL | CentOS |

    +--------+---------+--------+--------+

    找出所有的叶节点

    使用 LEFT JOIN 我们可以找出所有的叶节点:

    SELECT

    distributions.id, distributions.name

    FROM

    distributions

    LEFT JOIN distributions as child

    ON distributions.id = child.parent

    WHERE child.id IS NULL;

    结果如下:

    +----+--------------+

    | id | name |

    +----+--------------+

    | 3 | Knoppix |

    | 4 | Ubuntu |

    | 5 | Gentoo |

    | 7 | Fedora Core |

    | 9 | CentOS |

    | 10 | Oracle Linux |

    +----+--------------+

    邻接表模型的限制

    使用纯 SQL 处理邻接表模型即便在最好的情况下也是困难的。要获得一个分类的完整路径之前我们需要知道它的层次有多深。除此之外,当我们删除一个节点时我们需要格外的谨慎,因为这可能潜在的在处理过程中整个子树成为孤儿(例如删除『便携式小家电』则所有其子分类都成为孤儿了)。其中一些限制可以在客户端代码或存储过程中定位并处理。例如在存储过程中我们可以自下而上的遍历这个结构以便返回整棵树或一个路径。我们也可以使用存储过程来删除节点,通过提升其一个子节点的层次并重新设置所有其它子节点的父节点为这个节点,来避免整棵子树成为孤儿。

    嵌套集(Nested Set)模型

    由于使用纯 SQL 处理邻接表模型存在种种不便,因此 Mike Hillyer 郑重的介绍了嵌套集(Nested Set)模型。当使用这种模型时,我们把层次结构的节点和路径从脑海中抹去,把它们想象为一个个容器:

    99e2045ac5fbae631e332cd1786e5e8f.png

    可以看到层次关系没有改变,大的容器包含子容器。我们使用容器的左值和右值来建立数据表:

    CREATE TABLE nested (

    id INT NOT NULL AUTO_INCREMENT,

    name VARCHAR(32) NOT NULL,

    `left` INT NOT NULL,

    `right` INT NOT NULL,

    PRIMARY KEY (id)

    )

    ENGINE = InnoDB

    DEFAULT CHARACTER SET = utf8;

    需要注意 left 和 right 是 MySQL 的保留字,因此使用标识分隔符来标记它们。

    插入数据:

    INSERT INTO nested VALUES

    (1, 'Linux', 1, 20),

    (2, 'Debian', 2, 7),

    (3, 'Knoppix', 3, 4),

    (4, 'Ubuntu', 5, 6),

    (5, 'Gentoo', 8, 9),

    (6, 'Red Hat', 10, 19),

    (7, 'Fedora Core', 11, 12),

    (8, 'RHEL', 13, 18),

    (9, 'CentOS', 14, 15),

    (10, 'Oracle Linux', 16, 17);

    查看内容:

    SELECT * FROM nested ORDER BY id;

    可以看到:

    +----+--------------+------+-------+

    | id | name | left | right |

    +----+--------------+------+-------+

    | 1 | Linux | 1 | 20 |

    | 2 | Debian | 2 | 7 |

    | 3 | Knoppix | 3 | 4 |

    | 4 | Ubuntu | 5 | 6 |

    | 5 | Gentoo | 8 | 9 |

    | 6 | Red Hat | 10 | 19 |

    | 7 | Fedora Core | 11 | 12 |

    | 8 | RHEL | 13 | 18 |

    | 9 | CentOS | 14 | 15 |

    | 10 | Oracle Linux | 16 | 17 |

    +----+--------------+------+-------+

    我们是如何确定左编号和右编号的呢,通过下图我们可以直观的发现只要会数数即可完成:

    fba6d111ec9631ed0ed5271b76d1caa1.png

    回到树形模型该怎么处理,通过下图,对数据结构稍有概念的人都会知道,稍加改动的先序遍历算法即可完成这项编号的工作:

    f557ddf98a0047b50f5d1ab3109c0b68.png

    获取整棵树

    一个节点的左编号总是介于其父节点的左右编号之间,利用这个特性使用 self-join 链接到父节点,可以获取整棵树:

    SELECT node.name

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND parent.name = 'Linux'

    ORDER BY node.`left`;

    结果如下:

    +--------------+

    | name |

    +--------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Red Hat |

    | Fedora Core |

    | RHEL |

    | CentOS |

    | Oracle Linux |

    +--------------+

    但是这样我们丢失了层次的信息。怎么办呢?使用 COUNT() 函数和 GROUP BY 子句,可以实现这个目的:

    SELECT

    node.name, (COUNT(parent.name) - 1) AS depth

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    GROUP BY node.name

    ORDER BY ANY_VALUE(node.`left`);

    需要注意 MySQL 5.7.5 开始默认启用了 only_full_group_by 模式,让 GROUP BY 的行为与 SQL92 标准一致,因此直接使用 ORDER BY node.`left` 会产生错误:

    ERROR 1055 (42000): Expression #1 of ORDER BY clause is not in GROUP BY clause and contains nonaggregated column 'test.node.left' which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by

    使用 ANY_VALUE() 是避免这个问题的一种的途径。

    结果如下:

    +--------------+-------+

    | name | depth |

    +--------------+-------+

    | Linux | 0 |

    | Debian | 1 |

    | Knoppix | 2 |

    | Ubuntu | 2 |

    | Gentoo | 1 |

    | Red Hat | 1 |

    | Fedora Core | 2 |

    | RHEL | 2 |

    | CentOS | 3 |

    | Oracle Linux | 3 |

    +--------------+-------+

    稍作调整就可以直接显示层次:

    SELECT

    CONCAT(REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    GROUP BY node.name

    ORDER BY ANY_VALUE(node.`left`);

    结果相当漂亮:

    +-----------------+

    | name |

    +-----------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Red Hat |

    | Fedora Core |

    | RHEL |

    | CentOS |

    | Oracle Linux |

    +-----------------+

    当然客户端代码可能会更倾向于使用 depth 值,对返回的结果集进行循环,Web 开发人员可以根据其增大或减小使用

    / 或
    • /
    等。

    获取节点在子树中的深度

    要获取节点在子树中的深度,我们需要第三个 self-join 以及子查询来将结果限制在特定的子树中以及进行必要的计算:

    SELECT

    node.name, (COUNT(parent.name) - ANY_VALUE(sub_tree.depth) - 1) AS depth

    FROM

    nested AS node,

    nested AS parent,

    nested AS sub_parent,

    (

    SELECT

    node.name, (COUNT(parent.name) - 1) AS depth

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.name = 'Red Hat'

    GROUP BY node.name, node.`left`

    ORDER BY node.`left`

    ) AS sub_tree

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.`left` BETWEEN sub_parent.`left` AND sub_parent.`right`

    AND sub_parent.name = sub_tree.name

    GROUP BY node.name

    ORDER BY ANY_VALUE(node.`left`);

    结果是:

    +--------------+-------+

    | name | depth |

    +--------------+-------+

    | Red Hat | 0 |

    | Fedora Core | 1 |

    | RHEL | 1 |

    | CentOS | 2 |

    | Oracle Linux | 2 |

    +--------------+-------+

    寻找一个节点的直接子节点

    使用邻接表模型时这相当简单。使用嵌套集时,我们可以在上面获取子树各节点深度的基础上增加一个 HAVING 子句来实现:

    SELECT

    node.name, (COUNT(parent.name) - ANY_VALUE(sub_tree.depth) - 1) AS depth

    FROM

    nested AS node,

    nested AS parent,

    nested AS sub_parent,

    (

    SELECT

    node.name, (COUNT(parent.name) - 1) AS depth

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.name = 'Red Hat'

    GROUP BY node.name, node.`left`

    ORDER BY node.`left`

    ) AS sub_tree

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.`left` BETWEEN sub_parent.`left` AND sub_parent.`right`

    AND sub_parent.name = sub_tree.name

    GROUP BY node.name

    HAVING depth = 1

    ORDER BY ANY_VALUE(node.`left`);

    结果:

    +-------------+-------+

    | name | depth |

    +-------------+-------+

    | Fedora Core | 1 |

    | RHEL | 1 |

    +-------------+-------+

    获取所有叶节点

    观察带编号的嵌套模型,叶节点的判断相当简单,右编号恰好比左编号多 1 的节点就是叶节点:

    SELECT id, name FROM nested WHERE `right` = `left` + 1;

    结果如下:

    +----+--------------+

    | id | name |

    +----+--------------+

    | 3 | Knoppix |

    | 4 | Ubuntu |

    | 5 | Gentoo |

    | 7 | Fedora Core |

    | 9 | CentOS |

    | 10 | Oracle Linux |

    +----+--------------+

    获取单个节点的完整路径

    仍然是使用 self-join 技巧,不过现在无需顾虑节点的深度了:

    SELECT parent.name

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.name = 'CentOS'

    ORDER BY parent.`left`;

    结果如下:

    +---------+

    | name |

    +---------+

    | Linux |

    | Red Hat |

    | RHEL |

    | CentOS |

    +---------+

    聚集操作

    我们添加一张 releases 表,来展示一下在嵌套集模型下的聚集(aggregate)操作:

    CREATE TABLE releases (

    id INT NOT NULL AUTO_INCREMENT,

    distribution_id INT NULL,

    name VARCHAR(32) NOT NULL,

    PRIMARY KEY (id),

    INDEX distribution_id_idx (distribution_id ASC),

    CONSTRAINT distribution_id

    FOREIGN KEY (distribution_id)

    REFERENCES nested (id)

    ON DELETE CASCADE

    ON UPDATE CASCADE

    )

    ENGINE = InnoDB

    DEFAULT CHARACTER SET = utf8;

    加入一些数据,假设这些数据是指某个软件支持的发行版:

    INSERT INTO releases (distribution_id, name) VALUES

    (2, '7'), (2, '8'),

    (4, '14.04 LTS'), (4, '15.10'),

    (7, '22'), (7, '23'),

    (9, '5'), (9, '6'), (9, '7');

    那么,下面的查询可以知道每个节点下涉及的发布版数量,如果这是一个软件支持的发布版清单,或许测试人员想要知道他们得准备多少种虚拟机吧:

    SELECT

    parent.name, COUNT(releases.name)

    FROM

    nested AS node ,

    nested AS parent,

    releases

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    AND node.id = releases.distribution_id

    GROUP BY parent.name

    ORDER BY ANY_VALUE(parent.`left`);

    结果如下:

    +-------------+----------------------+

    | name | COUNT(releases.name) |

    +-------------+----------------------+

    | Linux | 9 |

    | Debian | 4 |

    | Ubuntu | 2 |

    | Red Hat | 5 |

    | Fedora Core | 2 |

    | CentOS | 3 |

    +-------------+----------------------+

    如果层次结构是一个分类目录,这个技巧可以用于查询各个类别下有多少关联的商品。

    添加节点

    再次回顾这张图:

    fba6d111ec9631ed0ed5271b76d1caa1.png

    如果我们要在 Gentoo 之后增加一个 Slackware,这个新节点的左右编号分别是 10 和 11,而原来从 10 开始的所有编号都需要加 2。我们可以:

    LOCK TABLE nested WRITE;

    SELECT @baseIndex := `right` FROM nested WHERE name = 'Gentoo';

    UPDATE nested SET `right` = `right` + 2 WHERE `right` > @baseIndex;

    UPDATE nested SET `left` = `left` + 2 WHERE `left` > @baseIndex;

    INSERT INTO nested (name, `left`, `right`) VALUES

    ('Slackware', @baseIndex + 1, @baseIndex + 2);

    UNLOCK TABLES;

    使用之前掌握的技巧看一下现在的情况:

    SELECT

    CONCAT(REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    GROUP BY node.name

    ORDER BY ANY_VALUE(node.`left`);

    结果为:

    +-----------------+

    | name |

    +-----------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Slackware |

    | Red Hat |

    | Fedora Core |

    | RHEL |

    | CentOS |

    | Oracle Linux |

    +-----------------+

    如果新增的节点的父节点原来是叶节点,我们需要稍微调整一下之前的代码。例如,我们要新增 Slax 作为 Slackware 的子节点:

    LOCK TABLE nested WRITE;

    SELECT @baseIndex := `left` FROM nested WHERE name = 'Slackware';

    UPDATE nested SET `right` = `right` + 2 WHERE `right` > @baseIndex;

    UPDATE nested SET `left` = `left` + 2 WHERE `left` > @baseIndex;

    INSERT INTO nested(name, `left`, `right`) VALUES ('Slax', @baseIndex + 1, @baseIndex + 2);

    UNLOCK TABLES;

    现在,数据形如:

    +-----------------+

    | name |

    +-----------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Slackware |

    | Slax |

    | Red Hat |

    | Fedora Core |

    | RHEL |

    | CentOS |

    | Oracle Linux |

    +-----------------+

    删除节点

    删除节点的操作与添加操作相对,当要删除一个叶节点时,移除该节点并将所有比该节点右编码大的编码减 2。这个思路可以扩展到删除一个节点及其所有子节点的情况,删除左编码介于节点左右编号之间的所有节点,将右侧的节点编号全部左移该节点原编号宽度即可:

    LOCK TABLE nested WRITE;

    SELECT

    @nodeLeft := `left`,

    @nodeRight := `right`,

    @nodeWidth := `right` - `left` + 1

    FROM nested

    WHERE name = 'Slackware';

    DELETE FROM nested WHERE `left` BETWEEN @nodeLeft AND @nodeRight;

    UPDATE nested SET `right` = `right` - @nodeWidth WHERE `right` > @nodeRight;

    UPDATE nested SET `left` = `left` - @nodeWidth WHERE `left` > @nodeRight;

    UNLOCK TABLES;

    可以看到 Slackware 子树被删除了:

    +-----------------+

    | name |

    +-----------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Red Hat |

    | Fedora Core |

    | RHEL |

    | CentOS |

    | Oracle Linux |

    +-----------------+

    稍加调整,如果对介于要删除节点左右编号直接的节点对应编号左移 1,右侧节点对应编号左移 2,则可以实现删除一个节点,其子节点提升一层的效果,例如我们尝试删除 RHEL 但保留它的子节点:

    LOCK TABLE nested WRITE;

    SELECT

    @nodeLeft := `left`,

    @nodeRight := `right`

    FROM nested

    WHERE name = 'RHEL';

    DELETE FROM nested WHERE `left` = @nodeLeft;

    UPDATE nested SET `right` = `right` - 1, `left` = `left` - 1 WHERE `left` BETWEEN @nodeLeft AND @nodeRight;

    UPDATE nested SET `right` = `right` - 2 WHERE `right` > @nodeRight;

    UPDATE nested SET `left` = `left` - 2 WHERE `left` > @nodeRight;

    UNLOCK TABLES;

    结果为:

    SELECT

    CONCAT(REPEAT(' ', COUNT(parent.name) - 1), node.name) AS name

    FROM

    nested AS node,

    nested AS parent

    WHERE

    node.`left` BETWEEN parent.`left` AND parent.`right`

    GROUP BY node.name

    ORDER BY ANY_VALUE(node.`left`);

    +----------------+

    | name |

    +----------------+

    | Linux |

    | Debian |

    | Knoppix |

    | Ubuntu |

    | Gentoo |

    | Red Hat |

    | Fedora Core |

    | CentOS |

    | Oracle Linux |

    +----------------+

    本文 2016-03-23 首次发表于 SegmentFault.com。

    展开全文
  • 您会问“python中应该使用什么数据结构来组织这些组?”自顶向下编程一个关键原则是,决定了将对该结构执行操作、它们相对频率和任何其他标准(例如简单性和内存使用率)...的结构中,新子级别上每...

    您会问“在python中应该使用什么数据结构来组织这些组?”在

    自顶向下编程的一个关键原则是,在决定了将对该结构执行的操作、它们的相对频率和任何其他标准(例如简单性和内存使用率)之前,您不会决定抽象数据结构的实现。您尚未说明该信息,因此我们无法推荐特定的实现。在

    我可以想出很多方法来做你要做的事情:树、列表中的列表、字典中的字典等等。每种方法都有其优缺点。我确实想知道一点。在您的结构中,新子级别上的每个项目都以“01”开头,但“02.01.02:克里斯,皮特”除外,它以“02”开头。这是故意的吗?如果您保持其他明显的编号,这将打开一些更简单的实现。在

    在您的评论中添加信息后,我建议您使用嵌套列表。每个数据项都有一个以零结尾的索引序列,结构中的任何其他内容都是一个包含其他数据项和列表的列表。在您的例子中,如果我们让整个结构命名为a,那么项01是a[1][0],项01.01在a[1][1][0],项02.01.02在a[2][1][2][0],依此类推。这种结构允许以后插入更多的项目,因此我们可以轻松地添加项目01.01.01,而不会干扰其他项目。不需要在结构中存储项编号:它们是从结构中数据项的位置直接推断出来的。在

    这个实现还允许整个结构有一个数据项,它有一个空的项号,并存储在a[0]中。丢失的数据项可以用None标记,空白项可以是另一个空项,如''。下面是显示示例结构的代码和打印出来的代码。在def print_structure(structure, level=''):

    """Iterate through a heirarchical data structure, printing the data

    items with their level numbers"""

    for i, item in enumerate(structure):

    if i == 0:

    # Process each data item appropriately

    if item is not None:

    print(level + ' : ' + str(item))

    else:

    new_level = format(i, '02')

    if level:

    new_level = level + '.' + new_level

    print_structure(item, new_level)

    a = [None,

    ['Tony, John, Meredith',

    ['Alex, Fred, Melissa']],

    ['Alley, Henry, Natalie',

    [None,

    ['?'],

    ['Chris, Pete']]],

    ['Andrew',

    ['Nancy, Peter, Harold']]]

    print_structure(a)

    在这个实现中,每个“组”都是一个字符串。我把组'?'放在你说存在一个组的地方,但没有说明它是什么;我把None放在你没有说存在数据项的地方。要修改结构的处理,只需更改注释Process each data item appropriately后的两行。上面代码的打印输出是

    ^{pr2}$

    保存到JSON和从JSON恢复很容易。这应该可以满足您的需要,当然,也可以对结构或代码进行一些修改。在

    展开全文
  • TreeTime是使用链接树而不是表平面列表常规数据组织,管理和分析工具。 树是一种层次结构,可将数据分为单位和子单位。 可以递归计算数学函数(总和,差,均值,比率)。 链接树是它们之间共享数据不同树。...
  • 我们从来没有听说过数据结构,从来没有注意到对数据进行合理的组织能够大幅度提升程序运行效率。 第1层次:“我听说过散列表,虽然不太明白,但感觉它很强大。” 第1层次是鸡尾酒会[2]水平认识度。达到这个...

    我们对数据结构的理解达到了什么层次?我们需要达到的层次是什么?

    第0层次:“数据结构是什么?”

    第0层次是指对数据结构一无所知。我们从来没有听说过数据结构,从来没有注意到对数据进行合理的组织能够大幅度提升程序的运行效率。

    第1层次:“我听说过散列表,虽然不太明白,但感觉它很强大。”

    第1层次是鸡尾酒会[2]水平的认识度。在达到这个层次后,我们至少讨论过基本的数据结构。我们听说过一些像搜索树和散列表这样的基本数据结构,或许还注意到它们所支持的一些操作。但是,在程序中使用它们或者在技术面试中熟练分析它们仍然非常困难。

    第2层次:“这个问题看来需要用堆才能搞定。”

    在进入第2层次后,我们开始进入状态。我们已经熟练地掌握了数据结构的基础知识,可以在程序中熟练地使用各种数据结构,并对哪种类型的数据结构适用于哪种类型的编程任务有着良好的感觉。

    第3层次:“我只用自己手工定制的数据结构。”

    第3层次是最高级的层次,适合专家级程序员和计算机科学家,他们已经不满足仅仅以客户的身份使用现有的数据结构的实现。在进入这个层次之后,我们对基本数据结构的所有细节了如指掌,对它们的实现方式也是烂熟于心。

    最大的提升空间就是提升到第2层次。大多数程序员总会在某个时刻需要以客户的身份使用基本的数据结构,如堆、搜索树和散列表。《算法详解(卷1)》第4章至卷2第6章的主要目标是帮助读者把数据结构的理解能力提升到这个层次,并把注意力集中在它们所支持的操作以及它们的标准应用上。大多数现代编程语言的标准库提供了这些数据结构,我们可以在程序中便捷地使用它们。

    高级程序员有时候需要从头实现某种数据结构的自定义版本。第4-12章都包含一个关于这些数据结构的典型实现的小节。这些小节适合那些希望把自己对数据结构的理解提升到第3层次的读者。

    《算法详解(卷1)》第4章至卷2第6章到底有哪些内容?

    • 主方法

    本章讨论决定递归算法的运行时间的“黑盒”方法,并讨论递归算法的一些关键特性,然后推导出算法的运行时间上界。这种“主方法”适用于读者所看到的绝大多数分治算法,包括Karatsuba的整数相乘算法(第1.3节)和Strassen的矩阵相乘算法(第3.3节)[1]。本章还将描述算法研究中一个更通用的理论:对新奇的算法思路进行适当的评估常常需要不直观的数学分析。

    在第4.1节介绍了递归过程之后,我们将在第4.2节提供主方法的正式定义,并观察它的6个应用例子(第4.3节)。第4.4节讨论了主方法的证明,着重强调它的3种著名情况背后的含义。这个证明非常优雅地建立在第1.5节对MergeSort算法分析的基础之上。

    • 快速排序(QuickSort

    本章讨论快速排序(QuickSort)。如果要排个“算法名人堂”,快速排序应该能够第一批入选。在高级层次上地描述了该算法的工作原理之后(第5.1节),我们讨论怎样在线性时间内根据一个“基准(pivot)元素”对数组进行划分(第5.2节),并讨论如何选择良好的基准元素(第5.3节)。第5.4节讨论了随机化的QuickSort,第5.5节证明了它对n个元素的数组进行排序的渐进性平均运行时间为O(nlogn)。第5.6节证明不会有任何“基于比较”的排序算法能够比O(nlogn)更快,从而为排序的讨论画上了一个完美的句号。

    • 线性时间级的选择

    本章研究选择问题,它的目的是在一个未排序的数组中寻找第i小的元素。如果使用排序方法,很容易在O(n log n)时间内解决这个问题,但是我们想要做得更好。

    第6.1节描述了一种极端实用的随机化算法,它的精神与随机化的QuickSort非常相似,但它的平均运行时间达到了线性时间。第6.2节提供了这个算法的优雅分析,有一种很好的方法可以按照简单的掷硬币试验来推进这个算法,证明它具有线性时间期望值。

    倾向于理论的读者可能会疑惑怎么可能在不借助随机化的情况下在线性时间内解决选择问题。第6.3节描述了该问题的一种著名的确定性算法,参与该算法的图灵奖得主多于我所知道的其他任何算法的。它是一种确定性的算法(即不允许使用随机化),建立在一种独特的“中位的中位元素”思路之上,以保证选择了良好的基准元素。第6.4节证明了它的线性时间上界,这可不是个简单的任务!

    本章假设读者已经熟悉第5.2节的可以在线性时间内围绕一个基准元素对数组进行划分的Partition子程序,并对基准元素的好坏具有良好的直觉。

    • 图的基础知识免费

    本章将会简单地介绍图的概念、图的用途以及计算机程序中常见的图表示形式。接下来的两章将深入讨论一些著名的与图有关的实用算法。

    • 图的搜索及其应用

    本章讨论与图的搜索及其应用有关的基础知识。本章讨论的内容有一个特点,就是我们将要讨论的所有算法都具有令人惊叹的高速度(具有较小常数因子的线性时间),但它们的工作方式并不是特别容易理解。本章的重点——只用两遍深度优先的搜索就完成了有向图的强连通分量的计算(见2.6节),生动地描述了高速的算法往往需要我们对问题的结构具有深刻的洞察力。

    本章首先是概述内容(见2.1节),描述了一些为什么要关注图的搜索的原因,并描述了在不进行任何冗余工作的前提下对图进行搜索的一种通用策略。本节还对两种重要的搜索策略——宽度优先的搜索(BFS)和深度优先的搜索(DFS)——进行了高层次的描述。2.2节和2.3节详细描述了BFS,包括它在最短路径计算和无向图的连通分量的计算方面的应用。2.4节和2.5节深入探讨了DFS,并讨论了如何用它计算有向无环图的拓扑顺序(相当于在遵循优先级约束的前提下对任务进行序列化)。2.6节使用DFS在线性时间内计算有向图的强连通分量。2.7节解释了为什么这种快速图元可用于对Web的结构进行探索。

    • Dijkstra最短路径算法

    Dijkstra最短路径算法[1]。这个算法适用于边的长度均不为负数的有向图,它计算从一个起始顶点到其他所有顶点的最短路径的长度。在正式定义这个问题(3.1节)之后,我们讲解这个算法(3.2节)以及它的正确性证明(3.3节),然后介绍一个简单直接的实现(3.4节)。在第4章中,我们将看到这种算法的一种令人惊叹的快速实现,它充分利用了堆这种数据结构。

    • 堆数据结构

    本书剩余的3章分别讨论3种极为重要并且广泛使用的数据结构:堆、搜索树和散列表。我们的目标是了解这些数据结构所支持的操作(以及它们的运行时间),并通过应用实例培养读者识别哪种数据结构适用于哪种类型问题的能力。另外,我们还可以对它们的幕后实现方式有所了解。我们首先讨论堆,这种数据结构可以帮助我们实现最小值或最大值的快速计算。

    • 搜索树

    与堆相似,搜索树也是一种存储一个不断变化的与键相关联的对象(可能还有大量其他数据)集合的数据结构。它维护它所存储的对象的整体顺序,并支持比堆更丰富的操作集合,其代价就是需要更多的额外空间,并且有些操作的运行速度比堆更慢一些。在讨论“为什么(应用)”和“怎么样(可选的实现细节)”之前,我们首先讨论“什么(即支持的操作)”。

    • 散列表和布隆过滤器

    在本书的最后一章,我们讨论一种极其实用并且被广泛使用的数据结构,即散列表(又称散列映射)。与堆和搜索树相似,散列表维护一组不断变化的与键相关联的对象(每个对象可能还包含许多其他数据)。与堆和搜索树不同,散列表并不维护与顺序有关的信息。散列表的存在意义是因为它支持超级快速的搜索,在这种场合下又称为查找。散列表可以告诉我们数据结构中是否存在某个对象,并且真的能够做到极端快速(远远快于堆或搜索树)。与往常一样,我们首先讨论散列表所支持的操作(见6.1节),然后讨论它的应用(见6.1节)以及一些可选的实现细节(见6.3节和6.4节)。6.5节和与6.6节讨论了布隆过滤器,它与散列表相似,它需要的空间更少,但付出的代价是偶尔会出现错误。

    选择正确的数据结构

    在软件的主要部分中,经常会用到数据结构。因此,对于严谨的程序员而言,知道在什么时候以及怎样使用数据结构是一项重要的基本技巧。数据结构的存在意义是它可以对数据进行组织,使我们可以快速、实用地访问数据。我们已经看到了数据结构的一些例子。2.2节介绍的用于实现线性时间的宽度优先的搜索的队列数据结构采用了线性形式组织数据,可以实现在常数级时间内从队列的头部删除对象或者在队列的尾部添加对象。2.4节介绍了在深度优先的搜索的迭代性实现中起到重要作用的堆栈数据结构,它允许我们在常数级时间内在堆栈的头部添加或删除对象。

    我们可以使用的数据结构还有很多。在本系列图书中,我们将看到堆、二叉搜索树、散列表、布隆过滤器以及并查集(union-find,详见本系列图书的卷3)。为什么要列出这几个看上去颇为复杂的例子呢?因为不同的数据结构支持不同的操作集合,所以它们适用于不同类型的编程任务。例如,宽度优先的搜索和深度优先的搜索具有不同的需求,分别由两种不同的数据结构满足。Dijkstra最短路径算法的快速实现(见4.4节)还有一些不同的需求,需要使用更为复杂的堆数据结构。

    不同的数据结构的利弊是什么?我们应该怎样在程序中选择具体的数据结构呢?一般而言,一种数据结构所支持的操作越多,这些操作的速度也就越慢,它们所需要的空间开销也就越大。爱因斯坦的这句名言恰如其分地说明了这一点:“尽可能让事情变得简单,但不能过于简单。”

    在实现一个程序时,重要的是认真考虑它需要频繁执行的操作。例如,我们是不是只关心一些对象是否存储在一个数据结构中?或者还需要以一种特殊的方式对它们进行排序?一旦理解了程序的需要,我们就可以遵循精简原则,选择一种支持所有必要的操作同时又没有太多不必要操作的数据结构。

    精简原则
    选择能够支持应用程序所需要的所有操作的最简单数据结构。
    展开全文
  • 数据库物理组织 数据库实现基础是文件,对数据库任何操作最终要转化为对文件操作。...数据库系统中数据的物理组织必须体现实体之间联系,支持数据库逻辑结构–各种数据模型。 **数据库要存储:数据描...

    数据库管理系统的层次结构之物理组织

    数据库实现的基础是文件,对数据库的任何操作最终要转化为对文件的操作。所以在数据库的物理组织中,基本问题是如何设计文件组织或者利用操作系统提供的基本的文件组织方法。
    数据库系统是文件系统的发展。文件系统中每个文件存储同质实体的数据,各文件是孤立的,没有体现实体之间的联系。数据库系统中数据的物理组织必须体现实体之间的联系,支持数据库的逻辑结构–各种数据模型。
    **数据库要存储:数据描述(数据外模式、模式、内模式)、数据本身、数据之间的联系、存取路径。**这些都要采用一定的文件组织方式组织、存储起来。

    1、数据字典的组织

    有关数据的描述存储在数据库的数据字典中。数据字段的特点是数据量比较小(与数据本身比)、使用频繁,因为任何数据库操作都要参照数据字典的内容。数据字典在网状、层次数据库中常常用一个特殊的文件来组织。所有关于数据的描述信息存放在一个文件中。
    关系数据库中数据字典的组织通常与数据本身的组织相同。数据字典按不同的内容在逻辑组织为若干字典表对应一个屋里文件,由关系数据库管理系统负责存储组织和管理。

    2、数据及数据联系的组织

    目前,操作系统提供的常用文件结构有顺序文件、索引文件、索引顺序文件、hash文件(杂凑文件)和B树类文件等。
    数据库中数据组织与数据之间的联系是紧密结合的。在数据的组织和存储中必须直接或间接、显示或隐含地体现数据之间的联系,这是数据库物理组织中主要考虑和设计的内容。
    在网状和层次数据库中常用邻接法和连接法实现数据之间的联系。对应到物理组织方式中,就要在操作系统已有的文件结构上实现数据库的存储组织和存取方法。
    举例: 在IMS数据库中,操作系统提供的低级存取方法有:顺序存取方法(SAM)、索引顺序存取方法(ISAM)、虚拟顺序存取方法(VSAM)和溢出顺序存取方法(OSAM)。IBS数据库管理系统在此基础上设计了层次顺序存取方法(HSAM)、层次索引存取方法(HISAN)、层次直接存取方法(HDAM)和层次索引直接存取方法(HISAM)4种数据库的存储组织的相应的存取方法。
    其中,HSAM按照片段值的层次序列码的次序顺序存放各片段值,而层次序列码体现了数据之间的父子和兄弟联系。这是一种典型的按物理邻接方式实现数据之间联系的方法。在这种存取方法中,整个数据库中不同片段型的数据均存储在一个SAM文件中。
    网状数据库中最常用的组织策略是各记录型分别用某种文件结构组织,记录型之间的联系–SET用指引元方式实现。即在每个记录型中增加数据库管理系统控制和维护的系统数据项–指引元,它和用户数据项并存于同一个记录中。
    关系数据库实现了数据表示的单一性。实体及实体之间的联系都用一种数据结构–“表”来表示,因此数据和数据之间的联系两者组织方式相同。在数据库的物理结构中,与数据字典类似,可以一个表对应一个物理文件,由操作系统负责存储管理,也可以多个表对应一个物理文件,由关系数据库管理系统负责存储组织和管理。

    3、存取路径的组织

    在网状和层次数据库中,存取路径是用数据之间的联系来表示的,因此与数据结合并固定。在关系数据库中存取路径和数据是分离的,对用户是隐蔽的。存取路径可以动态建立与删除。存取路径的物理组织通常采用B树类文件结构和hash文件结构。在一个关系上可以建立若干个索引。索引由用户用CREATE INDEX语句来建立,用DROP INDEX删除。在执行查询数据库管理系统查询优化模块也会根据优化策略自动简历索引,以提高查询效率。

    关系数据库中存取路径的建立是十分灵活的。

    展开全文
  • 未显示需要 javascript 文档选项级别: 初级徐享忠 (xuxz02@21cn.com), 软件工程师... 现实世界大量的数据都具有层次结构,常见例子包括组织机构序列(如公司机构、部队编制、作战编成)、分类体系(如中图分...
  • 探讨了网格数据处理中的数据结构组织问题, 提出了一种动态、有较强适应性通用流形网格数据组织结构,并以不同实例验证了所提出数据结构在时间上即时有效性、存储空间上自适应性以及实现上简单性和层次性...
  • 图是对一类数据结构的统称,很多应用场景都可以表示为图。例如:下面要介绍员工组织图,材料清单图,道路系统等等。 有向/无向 有向图,一条边两个顶点具有某种方向或顺序。无向图,每条边只是简单连接两...
  • 指定用户定义层次结构中属性之间属性关系 : 您已了解本教程中内容,现在可以将属性层次...对于在层次结构中导航用户而言,这两类用户层次结构是相同。 使用自然层次结构时,如果您构成级别属性之间...
  • 实际上,每个计算机系统的存储设备都组织成一个存储器的层次结构这个层次结构里面,从上到下,设备的访问速度越来越慢,容量越来越大,并且每个字节的造价也越来越便宜。寄存器文件在层次结构中位于最顶部,也...
  • 作为一种抽象数据类型,树可以用来对一组元素进行层次的组织,是一种常见的数据结构。本文介绍了树这一基本概念之后,将主要介绍应用较为广泛二叉树结构,并详细说明二叉树四种遍历方式——前序遍历、中序...
  • 存储器层次结构

    2020-09-18 09:02:14
    存储器层次结构中的缓存 存储器层次结构概念小结 高速缓存存储器 通用告诉缓存存储器组织结构 直接映射高速缓存 组相联高速缓存 全相联高速缓存 有关写问题 一个真实高速缓存层次结构解剖 高速缓存参数...
  • 存储器的层次结构

    千次阅读 2008-09-29 13:14:00
    可以通过层次组织数据,是随着组织层次的递减,对各层次的访问比例也依次递减。让第二级存储器包含所有指令和数据,程序当前访问"簇"暂时存放第一级存储器。有时第一级缓存储器中的某个簇要换出到第二级...
  • 本文,我们将探讨这两种保存层次数据的方法。我将举一个在线食品店树形图例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下: 本文包含了一些代码例子来演示如何保存和获取数据。我选择PHP [3]...
  • 前言请跟着上一讲...分层次组织在管理上具有更高效率!数据管理基本操作之一:查找如何实现有效率查找?查找查找:根据某个给定关键字K,从集合R找出关键字与K相同
  • oracle 树结构数据层次分列显示

    千次阅读 2013-03-13 14:43:44
    实际应用, 树结构数据的应用是很广泛, 如书目录结构, 组织部门分级等!!!!!  如一本书目录   name code P_code 目录 MULU 0 第一章 zh_1 MULU 第一节 ji_1_1 zh_1 ...
  • 显示cmt层次结构-源码

    2021-02-12 04:36:49
    html小部件创建一系列可折叠树,以显示当前USFWS组织层次结构。 预期用途:检查所需更正。 背景 每年冬天,USFWS主要通过检查Web界面来更新Corporate Master Table。 尽管这往往会使联系信息保持最新状态,...
  • scapy-协议数据组织结构与细节

    千次阅读 2011-01-20 21:49:00
    这也许是OO永远讨论不完话题,其受到争议正是因为这两种方式都太灵活了,让人不能轻易以一个优点作为根据迅速推翻另一者,正是因为二者都很好,scapy则同时使用了二者,恰巧正是这种scapy使用方式将继承和...
  • RDBMS操作 图 树 层次结构 等特殊的数据结构时,我们通常采用2个主要方法: 1.基于迭代/递归 2.具体化描述数据结构附加信息。 一般模型有:员工组织图(树,层次结构);料表--BOM(有向图);...
  • 组织管理架构、目录路径等层次结构数据关系数据库解决起来稍微有点繁琐。SQL Server 2005提供了公用表表达式(CTE),可以使用递归CTE方式查询层次结构数据。本节将介绍一种使用hierarchyid数据类型解决...
  • RDBMS操作 图 树 层次结构 等特殊的数据结构时,我们通常采用2个主要方法:1.基于迭代/递归 2.具体化描述数据结构附加信息。一般模型有:员工组织图(树,层次结构);料表--BOM(有向图);道路系统(无向循环图)1.迭代...
  • 如何计算机建立恰当模型表示不同图形对象 如何组织图形对象描述数据以使存储这些数据所要空间最省检索处理这些数据的速度较快;基本概念 三维形体表示 非规则对象表示 层次建模;造型技术 基本图形元素 ...
  • 数据模型是指数据库的组织形式,它决定了数据库中数据之间联系表达方式,即把计算机表示客观事物及其联系的数据结构称为数据模型。本文详细讲述传统三大数据模型和空间数据模型。 一、数据模型概述 数据模型...
  • 数据结构和算法的运用 编写一个完整的程序的过程中,合理的数据结构和算法可以使的程序更加...树结构是代表结构中,元素存在一对多的层次关系; 图结构是代表结构中数据存在多对多多对多的任意关系。 这三种不同的数
  • 很难说明数据之间的层次关系树是一种重要的非线 性数据结构,它能很好地描述结构的分支关系和层次 关系,所以 windows文件管理系统和数据库系统, 树结构是信息的重要组织形式之一 71树的基本概念 7.11树的定义 树...
  • 针对现实世界许多关系复杂的数据如人类社会家谱各种社会组织机构,博弈交通等复杂事物或过程以及客观世界广泛存在具有分支关系或层次特性对象如操作系统文件构成人工智能和算法分析模型表示以及数据库...
  • 设计了它们维和维层次数据结构;表述了地理空间维、专题维和时间维概念层次上和物理层次上构成空间数据立方体方法;确定了地理空间维、专题维和时间维数据的多维数组组织方法,以及多维数据的数据文件和虚拟...
  • 数据结构数据类型

    2020-02-15 15:29:52
    结构是指一个系统或者材料之,互相关联元素排列、组织结构按类别可分为等级结构 (有层次的一对多)、网格结构(多对多)、晶格结构(临近个体互相连接)等。 什么是数据结构 相互之间存在一种或多种...
  • 线性表存储结构中数据直接按照前驱后继线性组织形式排列。的结构中数据节点以层方式排列,节点与节点之间是一种层次关系。但是,的结构中数据之间可以有任意关系,这就使得图的数据结构相对复杂...
  • 文章目录存储器层次结构存储技术随机访问存储器磁盘存储固态硬盘局部性对程序数据引用局部性局部性小结存储器层次结构存储器层次结构中的缓存高速缓存存储器通用高速缓存存储器组织结构直接映射高速缓存组相连高速...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,394
精华内容 557
关键字:

在数据组织的层次结构中