数据结构

数据结构描述了数据元素之间的关系,可以从逻辑结构和存储结构两个维度来分析。

逻辑结构分类

  • 集合,数据元素除了同属一个集合没有其他关系;
  • 线性结构,存在一个对一个的关系;
  • 树形结构,一个对多个的关系;
  • 复杂结构(图状结构、网状结构),数据元素之间存在多个对多个的关系。如下图:

enter image description here

存储(物理)结构分类

顺序表示、链接表示、散列(哈希)表示、索引表示(注意这里的存储结构是内存的结构,以二进制形式存储,外存的存储不一样)。

逻辑结构转变成物理结构

逻辑结构最终需要变成物理结构,计算机才能使用,但是逻辑结构不能直接变成物理结构,中间需要经过程序语言处理,就是说我们需要:

  1. 用程序语言的数据结构来表示逻辑结构
  2. 运行程序
  3. 程序语言的数据结构就变成了物理结构

逻辑结构 -> 程序语言的数据结构 -> 物理结构。

树形逻辑结构的程序语言表示

我们使用 JS 来描述树形逻辑结构,有两种方式:

嵌套表示(子表表示法)

var tree1 = [
    {
        name: 'L1',
        children: [
            {
                name: 'L2_1',
                children: [ { name: 'L3_1'} ]
            },

            {
                name: 'L2_2',
                children: [ { name: 'L3_1' } ]
            },
        ]
    }
];

首先,是一个数组,包含所有的 L1(一级)节点;然后,每个节点有 children 属性(数组),保存子节点。

问题:只有父 -> 子的关系,没有子 -> 父的关系。

扁平表示(父指针表示法)

var tree2 = [
    { id: 1, name: 'L1' },
    { id: 2, pId: 1, name: 'L2_1' },
    { id: 3, pId: 2, name: 'L3_1' },

    { id: 4, pId: 1, name: 'L2_2' },
    { id: 5, pId: 4, name: 'L3_2' },
];

首先,也是一个数组,包含所有节点,通过 id 唯一标识;然后,使用 id、pId 维护子 -> 父的关系。

问题:与嵌套表示的问题正好相反,有子 -> 父关系,没有父 -> 子关系。

在业务场景中用到了树形结构,要满足所有的业务需求,如果没有完整的父 -> 子、子 -> 父的关系,就会面临很多困难,当然可以用各种方式来实现业务需求,但是这里想给出一种规范的、简便的方式。

完整结构

使用 id、pId 建立子 -> 父关系;在父节点的 children 属性包含所有子节点,建立父 -> 子关系。这有就有了完整的父子关系,其实是一种图形逻辑结构,可以满足所有业务需求。

注意这里有两个关键点:

  • 每个节点应该有一个唯一的标志 id
  • 整个结构首先是一个数组,可以根据 id 获取任意节点

这里自己实现了一个工具库,可以把嵌套、扁平结构转变成完整结构。

树形结构的数据库存储

不管是文档型数据库还是关系型数据库,都可以使用嵌套、扁平的方式来存储。

嵌套方式问题:子节点可能没有 id,这样解析成完整结构的时候需要手动维护 id。

扁平方式问题:需要进行多次插入,即先插入一个父节点,得到 id 后,把子节点的 pId 赋值成 id 再插入子节点。