Элегантная обработка организационных деревьев в реляционных базах данных

MySQL
Элегантная обработка организационных деревьев в реляционных базах данных

Мы часто сталкиваемся с такими сценариями в разработке проекта: организационная структура предприятия, цепочка ответов на комментарии, категория продукта и другие древовидные структуры. Эта статья сочетает в себе информацию из Интернета и мою собственную практику в проекте, чтобы рассказать о нескольких способах работы с древовидной структурой.

Может быть много знакомых, которые столкнулись с этой проблемой.Первая мысль, что я сохраняю это на каждом куске данных.parent_idОн может удовлетворить потребности, чтобы его можно было найти слой за слоем, а если написать рекурсивный алгоритм, то можно получить всех его подчиненных или вышестоящих. Это достижимый путь, и мы не будем оценивать плюсы и минусы такого подхода.

Вот несколько распространенных способов борьбы с ним:

  • Список смежности
  • Таблица закрытия
  • Перечисление пути
  • Вложенные наборы

В этой статье в основном объясняется перечисление путей (перечисление путей), а другие типы показаны лишь кратко.Если вам нужно знать, вы можете щелкнуть ссылку для просмотра.

Список смежности

На следующем рисунке показана организационная структура простой структуры списка смежности, о которой мы говорили ранее.

邻接表结构的组织结构

Как получить данные

  • Чтобы получить прямой отдел в организации, нам нужно только запросить по идентификатору организации.
select * from org where parent_id =1；
  • Чтобы запросить все организации в организации, вам нужно рекурсивно + зациклить, чтобы получить подчиненные узлы дочерних элементов, внуков и т. д., что примерно записывается следующим образом:
public List<Org> getOrgTree(String parentId){
  List<Orgs> resultOrgs = new ArrayList<>();
  // 拿到下级组织
  List<Org> children = getChildren(parentId);
  resultOrgs.addAll(children);
  for(Org org :children){
    resultOrgs.addAll(getOrgTree(org.parentID));
  }
  return resultOrgs;  
}

Таблица закрытия

Этот метод представлен комментариями к сообщениям, структура данных хлопотная, заимствованнаяу-у-у. Краткое описание.com/afraid/951 не 742 против…На схеме модель базы данных выглядит следующим образом:

![](xiao-files.oss-cn-beijing.aliyuncs.com/picgo/закрытие таблицы (2).png)

предок хранит корневой идентификатор ответа, потомок хранит текущий идентификатор, а хранилище занимает место Теоретически для хранения отношения требуется O (n²) пространства.

-- 父查子,连表查询comment 和 comment_path 拿到4号的评论
select c.* from comment c 
left join comment_path cp on (c.id = cp.descendant) 
where cp.ancestor = 4 and depth = 1;
-- 查询4号的所有子评论
select c.* from comment c join comment_path cp on (c.id = cp.descendant) where cp.ancestor = 4;

Вложенные наборы

Решение с вложенным набором хранит информацию в каждом узле, каждый из которых соответствует набору своих потомков, а не непосредственному родителю узла.

В дизайне вложенных наборов манипуляции с деревом, вставка и перемещение узлов часто более сложны, чем в других моделях.

При вставке нового узла необходимо пересчитать все левые и правые значения, превышающие левое значение нового узла.

Вложенные множества слишком сложны, и я не до конца в них разбираюсь, в этой статье мы не будем их подробно представлять. может относиться кMySQL реализует модель вложенной коллекции

Перечисление пути

Этот метод берет в качестве примера организационную таблицу в проекте.Отличие от перечисления пути заключается в том, что вместо пути используется org_num.

В проекте мы договорились, что числовая длина каждого уровня равна 2, максимальный уровень — 20, количество дочерних узлов на уровне — 99, а максимальное количество хранимых узлов: 2 в 19-й степени узлов.

Иерархия выглядит следующим образом:

Несколько способов манипулирования данными

Соглашение orgNum — это номер узла, orgLen — длина номера узла.

  • Получить несколько слоев дочерних узлов узла
-- 在java代码中根据当前节点orgNum得到 orgLen和maxLength
select * from orgs where org_num like '#{orgNum}%' and length(org_num) > #{orgLen} and length(org_num) <=#{maxLength}
  • Получить все дочерние узлы узла
select * from orgs where org_num like '#{orgNum}%' and length(org_num) > #{orgLen}
  • Получите родительский узел или найдите родительский узел на несколько слоев выше.
-- 先在java代码中的根据当前节点orgNum, 计算得出要找节点的orgNum，
select * from orgs where org_num = #{orgNum}
  • удалить организационную структуру
-- 删除所有子节点，和查询所有子节点类型
delete from orgs where org_num like '#{orgNum}%' and length(org_num) > #{orgLen}
  • Движение узла
// 节点移动，更新当前节点的org_num以及所有下级子节点的org_num
// 如果牵扯到节点排序，则除了更新当前节点的orgNum外，还要考虑要移动到的同级节点的orders
  • Построение организационного дерева
// 先从数据库中得到某个节点本身rootOrg及所有下级节点OrgList
private OrgTreeDTO orgTreeGenerate(List<Org> OrgList, Org rootNode, Org parent) {
    List<Org> subNodes = OrgList.stream().filter(x ->
      x.getOrgNum().startsWith(rootNode.getOrgNum())
        && x.getOrgNum().length() == rootNode.getOrgNum().length() + OrgConst.ORG_NODE_LENGTH
        && !x.getId().equals(rootNode.getId())
    ).collect(Collectors.toList());
    OrgTreeDTO orgTreeDTO = new OrgTreeDTO().setId(rootNode.getId())
      .setName(rootNode.getName())
      .setOrders(rootNode.getOrders())
      .setType(rootNode.getType())
      .setChildren(subNodes.stream().map(x ->
        orgTreeGenerate(OrgList, x,rootNode)
      ).collect(Collectors.toList()));
   
    if(!ObjectUtils.isEmpty(parent)){
      orgTreeDTO.setParentId(parent.getId())
        .setParentName(parent.getName());
    }
    return orgTreeDTO;
  }

Вышеупомянутые методы могут почти удовлетворить большинство потребностей в корректировке организационной структуры.

Преимущество этого метода в том, что нужные данные можно получить из базы данных с помощью простого запроса, а конкретная сборка обрабатывается в java-коде.

Недостаток Если уровень слишком глубокий,org_numЭто будет становиться все длиннее и длиннее и влиять на эффективность запроса, поэтому глубина узла в проекте ограничена 20, что может удовлетворить практически все данные организационной структуры.

Суммировать

Это конец этой статьи.Если у вас есть похожие идеи дизайна или вопросы, добро пожаловать в обсуждение.

Ссылка на блог команды, добро пожаловать, чтобы нажать

​Теория уточняет направление практики, а практика выявляет достоверность теории.

Категории