DB로 트리구조 만들기 (조직도)

만드는 이유

• 회사의 조직도를 구성해야했다.
• 조직도는 트리구조로 되어있기에 DB로 트리구조를 표현할 방법이 필요했다.
• 이러한 트리구조는 이 외에도 댓글의 댓글의 댓글, 게시판 내의 하위 게시판등 계층형 구조(Hierachy structure)에 자주 쓰인다.

자료 조사

Models For Hierachial Data

Trees And Hierachies In SQL

• 위 두 자료를 주로 참고했다.
• 첫번째 자료가 큰 줄기를 잡아주고, 두번째 자료는 그 안에서 세부적인 변형들을 소개한다.

정리

• 크게 다음 네가지 방법이 있다.

1. Adjacency List (인접 리스트)
2. Path Enumeration (경로 열거)
3. Nested Sets (중첩 집합)
4. Closure Table (폐쇄 테이블)

각 방법 개요

1. 인접 리스트 - 자식 노드가 부모 노드의 아이디를 저장한다.
2. 경로 열거 - 자식까지 오는 경로 자체를 필드에 저장한다. ( '1/2/3/' )
3. 중첩 집합 - 구간 트리처럼, 자식노드와 부모노드를 한번에 조회하기 쉽도록 구간을 저장한다.
4. 폐쇄 테이블 - 쿼리를 위한, 관계테이블 하나를 더 만듬.

나의 선택과 이유

인접 리스트를 쓰기로 했다.

조직 규모가 100~300명으로 작은 것을 상정하였고, 규모가 작고 성장하는 만큼 조직개편이 잦을 수 있어 업데이트 비용도 줄여야 한다고 생각하였다. 무엇보다 빠른 개발을 위해 구현이 복잡하지 않아야 한다. 마지막 힌트로는 조직도를 불러올 때, 한 조직 아래의 조직만 불러오는 요청은 거의 없고 회사 전체의 조직을 불러오는 요청이 많을 것이다.

경로 열거와 중첩집합의 경우 조회에 특화되어 있지만, 수정이 복잡하고 비용이 많이 든다. 특히 한 노드의 부모-자식 관계만 바꾸더라도 하위 자식을 업데이트(경로 열거), 하거나 전체 테이블을 업데이트(중첩 집합) 해야 하기 때문에 안정화된 구조에서 적합하다. (지리적 데이터, 유전적 데이터, 권한 관리 등)

물론 아무리 수정이 많아도, 조직도를 조회하는 작업이 훨씬 많을 것이기 때문에 (특히나 이번처럼 결재를 올리기 위해 조직도를 보는 경우라면) 구현이 비교적 간단한 경로 열거도 고려해볼만 하긴 하다. 수정해야할 관계가 많아지는 경우 I/O가 부담스럽긴 하다.

중첩 집합은 I/O를 줄일 수 있는 변형(Binary Fraction)이 몇 가지 소개되긴 했다. 그런데 구현이 복잡해 보여서 패스했다. 확장성 측면에서도 너무 깊어지면 실수 정밀도가 문제가 될 수도 있을 것 같다.

폐쇄 테이블을 선택하는 기준은 3계층 이상, 계층별로 10개 노드 이상이면 고려해볼만 하다고 하다. (GPT피셜이지만 어느정도 납득이 간다.)

최종적으로는 업데이트에도 비용을 많이 쓰지 않되, 조회에도 빠른 속도가 필요하기 때문에 회사ID를 인덱싱해 쿼리 시간(재귀적인 I/O)을 줄이기로 결정하였다. 재귀적 쿼리로 불러오지 않고 company ID같은 공통 필드를 통해 조직도를 모두 부른 이후 이후 parentID를 바탕으로 조직도를 재구성하여 내보낸다.

재구성 시간이 들긴 하겠지만 해쉬맵과 참조를 이용하여 선형탐색 한 번 ( O(N)) 으로 구성 시간을 최소화 하고자 하였고, 이 동작은 메모리에서 일어나기 때문에 마찬가지로 최대 O(N)이 될 수 있는 반복적인 SQL동작 (I/O) 보다는 훨씬 낫다고 판단했다. 폐쇄 테이블에 드는 O(N^2)의 용량, 조직도 업데이트를 위해 폐쇄 테이블을 업데이트하는 시간도 절약할 수 있다.

최종 ERD

구현

모델

Organize

type Organize struct {
	ID             uint        `gorm:"primaryKey" json:"organize_id"`
	CompanyID      uint        `gorm:"index" json:"company_id"`
	Name           string      `json:"organize_name"`
	ParentID       *uint       `gorm:"index" json:"parent_id"`
	ParentOrganize *Organize   `gorm:"foreignKey:ParentID" json:"parent_organize"`
	Children       []*Organize `gorm:"foreignKey:ParentID;references:ID" json:"children,omitempty"`
	Members        []*Member    `gorm:"foreignKey:OrganizeID" json:"members,omitempty"`
}

Member

type Member struct {
	ID                  uint    `gorm:"primaryKey"`
	CompanyID           uint    `gorm:"index"`
	Company             Company `gorm:"foreignKey:CompanyID"`
	Name                string  `gorm:"size:100"`
	Email               string  `gorm:"size:100;unique"`
	Password            string  `gorm:"size:100"`
	//.. 생략
	OrganizeID          *uint                 `gorm:"index"`
	Organize            *Organize             `gorm:"foreignKey:OrganizeID"`
}

Company

type Company struct {
	ID                     uint                 `gorm:"primaryKey"`
	Name                   string               `gorm:"size:60"`
	//..생략
	Members                []*Member             `gorm:"foreignKey:CompanyID"`
	Organizes              []*Organize           `gorm:"foreignKey:CompanyID"`
}

핸들러

create company

• 회사를 생성하면서, companyID를 가지고, ParentID가 nil인 최상위 organize를 만든다.

func CreateCompany(tx *gorm.DB, company models.Company) (*models.Company, *models.Organize, error) {

	if tx.Error != nil {
		return nil, nil, errors.New("could not begin transaction")
	}

	// 회사 생성
	if err := tx.Create(&company).Error; err != nil {
		tx.Rollback()
		return nil, nil, errors.New("could not create company")
	}

	// 조직 생성
	organize := models.Organize{
		CompanyID: company.ID,
		Name:      company.Name,
		ParentID:  nil,
	}

	if err := tx.Create(&organize).Error; err != nil {
		tx.Rollback()
		return nil, nil, errors.New("could not create organize")
	}

	return &company, &organize, nil
}

func CreateCompanyHandler(db *database.Database) fiber.Handler {
	return func(c *fiber.Ctx) error {

		company := new(models.Company)
		if err := c.BodyParser(company); err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": err.Error()})
		}

		tx := db.DB.Begin()
		company, _, err := CreateCompany(tx, *company)
		if err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}
		if err := tx.Commit().Error; err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		return c.Status(fiber.StatusCreated).JSON(company)
	}
}

Add Organize

• 등록은 간단하다.
• companyID 와 organizeID 를 받아 하위의 organize를 생성한다.

func AddOrganizeHandler(db *database.Database) fiber.Handler {
	return func(c *fiber.Ctx) error {

		companyID, err := strconv.ParseUint(c.Params("companyID"), 10, 32)
		if err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": "invalid companyID"})
		}

		organizeID, err := strconv.ParseUint(c.Params("organizeID"), 10, 32)

		if err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": "invalid companyID"})
		}

		organizeRequest := dto.OrganizeRequest{}
		if err := c.BodyParser(&organizeRequest); err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": err.Error()})
		}

		//설정
		parentID := uint(organizeID)

		organize := models.Organize{
			Name:      organizeRequest.Name,
			CompanyID: uint(companyID), //회사 아이디
			ParentID:  &parentID,
		}

		if err := db.DB.Create(&organize).Error; err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		return c.SendStatus(fiber.StatusNoContent)
	}
}

Get Organizes

• 회사의 organize 전체를 가져오는 핸들러를 만들었다.
• GetOrganizes를 통해서 Company에 속한 organize를 가져와 해시맵으로 반환한다.
• buildTree로 참조를 이용해 재구성한다.

func GetOrganizesHandler(db *database.Database) fiber.Handler {
	return func(c *fiber.Ctx) error {
		companyID, err := strconv.Atoi(c.Params("companyID"))
		if err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": "invalid companyID"})
		}

		orgMap, err := GetOrganizes(c, db, uint(companyID))
		if err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		root, err := buildTree(orgMap)
		if err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}
		return c.JSON(root)
	}
}

func GetOrganizes(c *fiber.Ctx, db *database.Database, companyID uint) (map[uint]*dto.OrganizeResponse, error) {
	var organizes []models.Organize
	if err := db.DB.Preload("Members").Where("company_id = ?", companyID).Find(&organizes).Error; err != nil {
		return nil, err
	}

	orgMap := make(map[uint]*dto.OrganizeResponse)
	for _, organize := range organizes {
		organizeDTO := dto.MapOrganizeToResponse(organize)
		orgMap[organizeDTO.ID] = &organizeDTO
	}

	return orgMap, nil
}

func buildTree(orgMap map[uint]*dto.OrganizeResponse) (dto.OrganizeResponse, error) {

	var root *dto.OrganizeResponse
	for _, tempOrg := range orgMap {
		if tempOrg.ParentID != nil {
			parent, ok := orgMap[*tempOrg.ParentID]
			if !ok {
				return dto.OrganizeResponse{}, fiber.NewError(fiber.StatusInternalServerError, "parent not found")
			}
			parent.Children = append(parent.Children, tempOrg)
		} else if root == nil {
			root = tempOrg
		} else {
			return dto.OrganizeResponse{}, fiber.NewError(fiber.StatusInternalServerError, "multiple root found")
		}
	}

	if root == nil {
		return dto.OrganizeResponse{}, fiber.NewError(fiber.StatusInternalServerError, "root not found")
	}

	return *root, nil
}

• buildTree에서 root오류 (root 없음, root 두 개) 에 대해 최대한 검사해주려고 했다.
• root를 중심으로 반환하므로, 순환 참조 노드는 자연스럽게 배제된다. (오류 처리는 되지 않는다.)

Delete Organize

• Organize를 지울 때는 하위 Organize도 모두 지우고 Oraganize에 속해있던 Member도 해제해줘야 한다. (이 때문에 Member가 무조건 Organize에 속하지 않아도 되게 처리하였다.)

func DeleteOrganizeHandler(db *database.Database) fiber.Handler {
	return func(c *fiber.Ctx) error {
		organizeID, err := strconv.ParseUint(c.Params("organizeID"), 10, 32)
		if err != nil {
			return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{"error": "invalid organizeID"})
		}

		// 트랜잭션 시작
		tx := db.DB.Begin()
		if tx.Error != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": "could not start transaction"})
		}

		var organize models.Organize
		if err := tx.First(&organize, organizeID).Error; err != nil {
			return c.Status(fiber.StatusNotFound).JSON(fiber.Map{"error": "organize not found"})
		}

		// 모든 하위 조직 삭제
		if err := deleteSubOrganizes(tx, uint(organizeID)); err != nil {
			tx.Rollback()
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		// 해당 조직의 멤버 등록 해제
		if err := tx.Model(&organize).Association("Members").Clear(); err != nil {
			tx.Rollback()
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		// 조직 삭제
		if err := tx.Delete(&organize, uint(organizeID)).Error; err != nil {
			tx.Rollback()
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": err.Error()})
		}

		// 트랜잭션 커밋
		if err := tx.Commit().Error; err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{"error": "could not commit transaction"})
		}

		return c.SendStatus(fiber.StatusNoContent)
	}
}

// 모든 하위 조직을 재귀적으로 삭제하는 함수
func deleteSubOrganizes(tx *gorm.DB, parentID uint) error {
	var subOrganizes []models.Organize
	if err := tx.Where("parent_id = ?", parentID).Find(&subOrganizes).Error; err != nil {
		return err
	}

	for _, subOrganize := range subOrganizes {
		if err := deleteSubOrganizes(tx, subOrganize.ID); err != nil {
			return err
		}

		// 해당 조직의 멤버 등록 해제
		if err := tx.Model(&subOrganize).Association("Members").Clear(); err != nil {
			tx.Rollback()
			return err
		}

		//조직 삭제
		if err := tx.Delete(&subOrganize).Error; err != nil {
			return err
		}
	}

	return nil
}

기타

• 이렇게 재귀적인 구조를 기초로 코드를 짜고, Node의 위치 Update시에는 인접리스트 특성상, 가장 상위의 노드만 이동하면 되기 때문에 api 자체를 짜기는 쉽고, 이를 호출하는 UI논리구조를 짜기가 복잡할 것 같다.