가짜 나무: 더 간단한 UI를 위한 들여쓰기 사용

 (ratfactor.com)
4P by GN⁺ | ★ favorite | 댓글 1개
  • 계층형 UI가 필요해 보여도 먼저 확인할 것은 데이터가 정말 부모-자식 관계를 가져야 하는지, 아니면 그렇게 보이기만 하면 되는지임
  • 실제 트리가 필요 없다면 부모 ID 대신 전체 목록의 절대 정렬 순서와 indent 값만으로 화면상의 구조를 표현할 수 있음
  • Hiss 게임 에디터는 banana.eat 같은 이름을 정렬한 뒤 점(.) 뒤를 들여써 보여주며 네임스페이스처럼 보이는 UI를 만듦
  • 이 방식은 사용자가 항목을 위아래로 옮기고 들여쓰기/내어쓰기를 하는 워드프로세서식 편집에 가까워 트리 자료구조 부담을 줄임
  • 항목 간 관계를 실제로 조회하거나 유지해야 한다면 들여쓰기나 문자열 기호 해킹 대신 진짜 트리 모델이 필요함

트리가 아니라 트리처럼 보이는 목록

  • 애플리케이션에서 Foo, Bar 같은 동적 목록을 트리 뷰로 보여주려 하면 보통 각 항목에 부모 항목을 연결하는 구조를 떠올리게 됨
  • 관계형 데이터베이스에서는 예를 들어 parent 컬럼으로 부모 ID를 저장할 수 있음
    • Foo의 parent는 null
    • Foo 1의 parent는 Foo
    • Foo 1.a의 parent는 Foo 1
  • 이런 트리 데이터를 SQL로 가져오려면 재귀 CTE 같은 방식이 필요할 수 있음
  • 하지만 많은 목록에서는 실제 관계보다 사람이 보기 좋게 정리된 모양이 더 중요할 수 있음

들여쓰기 값을 데이터로 저장하는 방식

  • 실제 부모-자식 관계가 필요 없다면 목록을 다음 필드만으로 저장할 수 있음
    • id
    • sort
    • indent
    • name
  • sort는 하위 항목 내부 순서가 아니라 전체 목록의 절대 순서를 나타냄
  • indent는 항목 앞에 넣을 공간의 양을 그대로 나타내므로 화면 렌더링이 단순해짐
  • 편집 UI도 트리 조작보다 단순해질 수 있음
    • 사용자는 항목을 위아래로 이동할 수 있음
    • 항목을 들여쓰기하거나 내어쓸 수 있음
    • 필요하면 올바른 들여쓰기를 강제하는 간단한 규칙을 추가할 수 있음
  • 결과적으로 컴퓨터과학 교과서식 자료구조를 직접 조작하기보다, 워드프로세서에서 목록을 편집하는 경험에 가까워짐

Hiss의 점(.) 기반 가짜 네임스페이스

  • 텍스트 어드벤처 게임 에디터 Hiss는 banana, banana.eat, banana.peel 같은 이름을 UI에서 계층처럼 보여줌
  • HissScript에 실제 네임스페이스 기능을 구현한 것은 아님
  • 구현 방식은 단순함
    • 객체 이름을 알파벳순으로 정렬함
    • 이름에 점(.)이 있으면 앞부분을 잘라냄
    • 남은 부분을 들여써서 출력함
  • 예시 코드의 핵심 로직도 같은 흐름임
    • things.keys를 정렬함
    • 각 이름에 점이 있으면 들여쓰기 후 점 앞부분을 제거해 출력함
    • 점이 없으면 이름을 그대로 출력함
  • 이후 주어진 접두사를 가진 “부모” 항목이 존재하는지 확인하는 검사가 몇 줄 더 추가됨
  • 임의 깊이의 중첩도 추가할 수 있지만, 실제 필요가 생길 때까지 기다리는 상태임
  • 이 네임스페이스처럼 보이는 UI는 게임을 정리하는 사람에게는 중요하지만, 게임 에디터와 플레이어에게는 특별한 의미가 없음
    • 점이 들어간 이름도 그냥 이름임
    • 네임스페이스처럼 보이는 부분은 이름을 유일하게 유지하는 역할만 함

평면 목록으로 다루는 트리 비슷한 사례

  • Dave Long은 “저기술 실제 트리”로 경로와 정보를 평면 목록에 저장하는 방식을 제안함
  • 이는 banana.eat 예시와 비슷한 통찰임
  • find 출력처럼 다음 형태의 경로 목록을 생각할 수 있음
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • 깊이 우선 순회가 필요하면 경로를 사전순 정렬하면 됨
  • 너비 우선 순회가 필요하면 경로 구분자를 기준으로 경로를 뒤집고, 깊이를 맞추기 위해 빈 항목을 추가한 뒤 정렬할 수 있음
  • 이 예시는 개념을 보여주기 위한 것이며, 실제로는 구분자로 줄을 나눈 뒤 배열로 처리하는 방식이 자연스러움
  • 평면 목록은 전반적으로 다루기 좋고, 가능하면 항목을 plain old lists에 넣는 접근을 선호함

바닥 위 스크랩북 비유

  • 개인 스크랩북 작업에서는 사진, 메모, 엽서, 티켓 등을 바닥에 늘어놓고 그룹을 만들 수 있음
  • 사람에게는 그룹 관계가 분명해 보여도, 바닥 자체에는 그 관계를 강제하는 물리적 장치가 없음
  • 이 비유의 핵심은 표현된 관계와 실제 구조적 관계가 다를 수 있다는 점임
  • UI 목록도 마찬가지로, 사람에게 계층처럼 보이는 배치가 내부 데이터 모델의 실제 계층을 의미하지 않을 수 있음

실제 트리가 필요한 경우

  • 들여쓰기나 문자열 기호 기반 방식은 상황에 맞게 크게 조정해야 하며, 일반적인 프로그래밍 맥락에서는 해킹으로 취급될 가능성이 있음
  • 실제로 항목 간 관계를 알아야 한다면 부모 ID, 부모-자식 조인 테이블 등 데이터 모델에 맞는 진짜 트리 구조를 사용해야 함
  • 대규모 연구 프로젝트를 분류하는 상황처럼 물리적 파일 캐비닛과 폴더 수준의 조직력이 필요하다면 “바닥 방식”은 적합하지 않음
  • 항목 간 관계를 나중에 실제로 알아야 하는 프로젝트에서 들여쓰기나 문자열 안의 기호 개수로 구조를 흉내 내면, 프로젝트 수명과 유지보수 기간 내내 고통스러운 경로가 될 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 첫 번째 방식, 즉 “당연히 이 방법뿐”처럼 보이는 방식은 인접 리스트(adjacency list) 라고 부름
    두 번째 “훨씬 단순한 방법”은 전에 본 기억이 없고, 명백한 단점도 있지만 어떤 경우에는 충분해 보임
    세 번째 “네임스페이스화”는 구체화 경로(materialized path) 라고 부르며, 트리를 표현하는 또 다른 방식으로 중첩 집합(nested sets)도 있음: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    사람들이 관계형 데이터베이스를 진지하게 다루던 시절에는 모두 잘 알려진 내용이었고, 예를 들면 http://www.dbazine.com/oracle/or-articles/tropashko4/ 같은 글도 있음
    이제는 잊힌 지식처럼 보임

    • 예전 직장에서 가장 싫었던 순간 중 하나가, 문제를 설명하느라 엄청 애썼는데 누군가가 이미 이름도 있고 연구도 된 기존 개념이라고 알아보는 때였음
      문제의 여러 면을 직접 파악하는 중에는 그 개념의 기존 이름을 찾아내기가 정말 어렵다고 느낌
    • 맞는 말임. 요즘 뽑는 젊은 졸업생들은 모든 걸 NoSQL 문서에 우겨 넣고 데이터 모델링은 거의 생각하지 않으려 함
      결국 트리를 표시하는 모든 로직을 코드에서 처리하는데, 최신 관계형 데이터베이스와 일부 CTE만으로도 많은 사용 사례를 우아하게 공짜로 처리할 수 있어서 아쉬움
    • 잊힌 지식이라고 보긴 어려움. “Joe Celko's Trees and Hierarchies in SQL”이라는 책도 있음
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • 이 주제에 관심 있다면 우선 https://en.m.wikipedia.org/wiki/Joe_Celko의 책들을 찾아보는 걸 추천함

  • Postgres에는 이런 식으로 네이티브하게 동작하는 ltree 자료형과 검색 연산자가 있음: https://www.postgresql.org/docs/current/ltree.html
    예를 들면 CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');처럼 넣고
    SELECT path FROM test WHERE path <@ 'Top.Science';로 Top.Science와 Top.Science.Astronomy를 찾을 수 있음

    • 프로그래머 주의: ltree의 특이점 중 하나는 트리로 그리면 부모 노드가 될 중간 경로가 실제로 존재할 필요가 없다는 것임
      위 예시에서 Top.Science 레코드를 삭제해도 Top.Science.Astronomy 레코드는 잘려 나가지 않음
      ltree 값의 라벨은 구체화 경로를 통해 논리적 트리를 암시하지만, 암시된 모든 부모 노드에 해당하는 레코드의 존재를 강제하지는 않음
      애플리케이션에 따라 이게 정확히 원하는 동작일 수도 있고, 정반대일 수도 있음. 후자라면 무결성을 유지할 장치를 따로 둘 필요가 있음
    • 파일 경로를 저장하려면 구분자를 /로 쓸 수 있는지 궁금함
    • 성능 경험이 있는지 궁금함. 정규식 처리가 많아 보임
    • SQL Server에도 매우 비슷한 기능이 있고[1], 써본 바로는 꽤 잘 동작함
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • 같은 걸 JSON 컬럼으로도 할 수 있을까 궁금함. 그러면 노드에 문자열이 아닌 자료형도 쓸 수 있음
      다만 JSON 인덱스가 ltree 인덱스만큼 잘 동작하지 않을 수 있다는 우려가 있음

  • 여기서 문제는 구조 안의 가치가 대개 표시용 트리가 아니라 데이터의 계층 구조에 있다는 것임
    데이터를 순회하거나, 관계를 보여주거나, 재정렬하는 등의 작업을 하게 될 가능성이 큼
    데이터베이스의 자료구조에 시각적 정보를 담는 건 위험하고 근시안적으로 보임

    • 글쓴이가 이미 “사람들은 항상 부모-자식 관계를 정식으로 인코딩해야 한다고 생각하지만, 실제로는 그렇지 않을 때도 있고 중첩된 표시만 필요할 때도 있다”고 명시했는데, 거기에 대한 반응으로는 좀 이상함
      “아니, 그럴 리 없다”가 답인가?
      YAGNI가 유명한 설계 휴리스틱인 데는 이유가 있음. “항상 필요하다고 가정하라”는 맞지 않음
    • 아이러니하게도 여전히 데이터 안에서 부모 ID를 쓰고 있음
      최적화된 자료형의 전용 컬럼에 저장하는 대신 데이터 문자열 앞에 붙였을 뿐임
      숫자가 아닐 수도 있고 ID 컬럼이 아닐 수도 있지만, 다른 기대값을 가리키는 식별자라는 점은 그대로라서 형식이 바뀌었다고 부모 ID가 아니게 되지는 않음
    • 원문의 순서/들여쓰기 인코딩 방식에서도 부모-자식 관계는 쉽게 재구성할 수 있어야 함
      물론 부모 없는 자식 같은 잘못된 들여쓰기가 저장되지 않도록 보장해야 함
      그래서 가장 쉬운 방법은 먼저 순서/깊이로 저장하고, 필요한 기능을 구현할 때 부모/자식 모델로 마이그레이션하는 것이라고 봄
      단, “들여쓰기”는 렌더링할 공백 수가 아니라 트리에서의 깊이로 더 추상적으로 정의하는 게 좋음. 잘못된 데이터를 찾기 쉽고, 이후 마이그레이션도 쉬우며, 중첩된 /, 탭, 8칸, 4칸, 1칸 등 사용자별 렌더링 유연성도 생김
    • struct item_t { char key[255]; char display_value[255]; } 같은 자료구조가 있고, 키가 a/b/c처럼 일관된 경로 구분자를 가진다면 부모와 자식을 찾는 건 매우 쉬움
      최악의 경우 배열을 선형 탐색하면 되고, 정렬돼 있다면 부모에 도달할 때까지 이전 항목만 보면 됨
    • 강하게 동의함. 비정규화가 때로 좋은 선택일 수는 있지만, 이 경우가 합리적인 정당화라고 보지는 않음

  • 트리 형태 데이터가 많은 회사를 시작한 적이 있음. 트리 구조를 들여쓴 목록으로 바꾸는 건 O(n) 시간에 가능함
    당시 면접 질문 중 하나였고, 여러 SQL 데이터베이스에서 재귀 쿼리 없이도 트리 일부를 빠르게 가져와 렌더링할 수 있게 저장하는 방법들이 있음
    이런 개념을 이해하고 나면, 데이터를 제대로 트리로 저장하는 편이 이런 식의 들여쓰기보다 이점이 훨씬 많음

    • 그런 이점이 필요 없다면 별로 중요하지 않음

  • “SQL 쿼리로 관계형 데이터베이스에서 트리 구조 데이터를 가져오는 한 방법은 재귀 CTE(Common Table Expressions)를 쓰는 것인데, 이름만큼이나 재미있다”
    CTE는 재귀 CTE까지 포함해도 무서운 게 아니고, 익숙해지면 실제로 재미있다고 장담함

    • CTE가 딱히 재미있지는 않음. 관심 있는 부분을 디버깅하려고 CTE 탑 전체를 다른 SQL 창에 복사해 붙여넣는 건 내가 추구하는 오락이 아님
    • 정규화된 표현에서 트리 데이터를 조립할 때 재귀 CTE가 엄청 느렸음
      계층 깊이가 d인 노드 경로를 조립하려면 쿼리 결과를 얻는 시간이 최소 d배는 느려졌음
      장점은 트리 편집 작업이 싸다는 것이었지만, 읽기에 비하면 훨씬 드물게 일어났음
    • CTE는 괜찮음. 글쓴이는 이 정보를 테이블에 구워 넣는 대신, CTE로 포맷된 이름을 담은 뷰를 만들 수도 있었음

  • “사람들은 실제로 트리를 원하거나 필요로 하는 게 아니라, 트리처럼 보이는 것만 필요한 경우가 더 많다”는 점에서 HN과 Reddit의 차이를 보게 됨
    HN에서는 자식 댓글이 부모 댓글의 nextSibling이고, 부모의 들여쓰기 값에 1을 더해 트리처럼 보이게 함
    Reddit, 적어도 old.reddit.com에서는 자식 댓글이 실제로 부모 댓글 안에 중첩됨. 새 사이트는 잘 모르겠음

    • 실제 표시가 아니라 HTML 구조를 말하는 거지? 화면에 보이는 모습은 거의 동일함
    • 백엔드에 실제로 이렇게 저장된다고는 상상하기 어려움
      데이터에 대한 모든 작업이 트리 구조를 추론한 뒤 다시 암시적 트리 형식으로 번역하는 복잡한 난장판이 될 것임
    • 그렇다면 접기는 어떻게 동작하는지 궁금함

  • 글의 핵심 아이디어는 단순함. 문제에 맞는 구조를 쓰자는 것임
    다만 서사는 잘못됐다고 봄. 데이터베이스에서 트리를 가져오는 데 CTE가 꼭 필요한 건 아니고, 평평한 목록을 가져온 뒤 로컬에서 트리를 구성하면 됨. 이후 조작을 위해서도 어차피 그럴 가능성이 큼
    같은 논리라면 목록을 저장하려고 관계형 데이터베이스를 쓰는 사람에게도 텍스트 파일에 저장하라고 할 수 있음. 왜 네트워크 지연 비용을 치르나?
    반대로 제안된 구조는 충분히 큰 트리에서 가지를 옮기고 깊이를 바꾸려면 동작이 좋지 않음. 선형 비용이 들기 때문임
    처음부터 의도를 밝혔어야 함. 세 가지 예시를 설명한 뒤 결론에서 “트리가 필요하면 트리를 쓰라”고 무효화하지 말고. 다만 그걸 글 앞에 넣었으면 훨씬 덜 클릭베이트였을 것임

  • 몇 년 전 OpenGL에 대해 비슷한 깨달음을 얻었음. 계층적 3D 객체의 세계를 그릴 필요가 있는 게 아니라, 정렬된 삼각형 목록을 그리면 됐음
    그 생각이 머릿속 스위치를 켜 줬고, 여러 최적화가 아주 쉬워졌음

    • 맞음. 2000년 이후 3D 게임에서는 단순함이 큰 힘이 됨
      복잡한 엔티티 계층이 있는 게임에서도 렌더 큐에 넣을 때는 투명도 정렬 같은 이유로 평평한 구조로 접어야 하는 경우가 많음
      “사물의 평평한 목록”은 ECS/DOD의 기반이기도 함

  • 데이터베이스에서 이런 작업을 다루는 책이 통째로 있음
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • 모든 책이 초보자용이라고들 하더니, 좋네

  • 가짜 트리를 만드는 또 다른 방법은 JSON 블롭을 저장하는 것임
    데이터가 내부 관계만 가진다면 정렬 번호를 유일하고 순서 있게 유지하려는 것보다 더 쉬울 수 있음

    • 중첩 JSON으로 표현한 트리는 데이터베이스에 부모 참조를 저장해서 얻는 가상 트리보다 오히려 더 “진짜” 트리라고도 볼 수 있음
답변달기