팩토리오에서의 B-트리

 (razberry.substack.com)
4P by GN⁺ | ★ favorite | 댓글 1개
  • Database Internals 북클럽의 B-Tree 장을 읽은 뒤, 자료구조를 코드가 아니라 Factorio 공장 구조물로 구현해 개념을 시각적으로 검증함
  • BST는 키가 정렬 가능할 때만 왼쪽·오른쪽 분기가 가능하며, 값이 한쪽으로 몰리면 검색 효율이 선형 리스트 수준으로 떨어질 수 있음
  • 디스크 기반 저장에서는 BST의 재균형 비용과 여러 페이지 읽기가 부담이 되며, B-Tree는 한 노드에 여러 키를 담아 이 문제를 줄이는 구조임
  • Factorio 구현은 나무 상자와 보라색 필터 팔로 노드와 비교 연산을 표현하고, 임의의 아이템 정렬 순서를 정해 검색 경로를 만듦
  • B-Tree 버전은 노드당 3개 키와 4개 포인터를 사용해 2단계에서 BST보다 훨씬 많은 키를 담지만, 값 표현과 수동 정렬 문제가 남아 있음

BST와 B-Tree의 차이

  • 이진 검색 트리(BST) 는 각 노드가 하나의 키를 담고, 더 낮은 키는 왼쪽 노드로, 더 높은 키는 오른쪽 노드로 보냄
    • 예시는 루트 키 8, 왼쪽 3, 오른쪽 10으로 시작함
    • 키 값의 높고 낮음을 비교할 수 있는 정렬 가능한 값에서만 동작함
  • 값이 한쪽에만 많이 추가되면 BST의 균형이 깨짐
    • 최악의 경우 8 -> 10 -> 14 같은 선형 정렬 리스트와 거의 같아짐
    • 피벗으로 10을 루트에 두고 8, 14를 양쪽에 배치하는 식으로 불균형을 고칠 수 있음
  • 디스크 기반 저장에서는 BST가 불리함
    • 재균형을 계속 맞추면 디스크와 포인터를 자주 갱신해야 함
    • 이웃 노드가 서로 다른 페이지에 저장될 수 있어, 한 번의 검색에도 여러 페이지를 읽을 수 있음
  • B-Tree는 노드 하나에 여러 키를 담고, 키 수 + 1개의 포인터로 자식 노드를 가리킴
    • 예시의 [17 | 24] 노드는 17보다 작은 키, 17과 24 사이의 키, 24보다 큰 키를 가진 세 자식 노드로 분기함

Factorio 안에서 구현한 검색 트리

  • Factorio는 공장 건설 게임이며, 구현에서는 각 트리 노드를 게임 안 구조물로 표현함
  • 먼저 단순 BST를 만듦
    • 각 노드는 하나의 키를 담는 나무 상자와 다른 노드로 이어지는 두 경로를 가짐
    • 재료 사이에 기본 비교 방식이 없어서 wood, coal, stone, brick, copper, iron, steel 순서로 임의의 정렬 기준을 둠
    • 보라색 필터 팔이 비교 검사를 맡음
      • 첫 번째 노드에서는 한 팔이 아이템이 brick과 같은지 확인함
      • 두 번째 팔은 wood, coal, stone처럼 brick보다 작은지 검사함
      • 세 번째 팔은 copper, iron, steel처럼 더 큰 값을 걸러냄
    • 오른쪽 위에는 컨베이어 벨트에 잘못 들어온 아이템을 치우는 가비지 컬렉터도 둠
  • B-Tree 구현은 노드 하나에 더 많은 구조물이 필요함
    • 각 노드에 3개 키, 3개의 필터 팔, 3개의 나무 상자, 4개의 자식 포인터를 둠
    • 같은 깊이에서 더 많은 정보를 담을 수 있음
    • 2단계에서 BST는 2개 키를 담지만, B-Tree는 12개 키를 담음
    • 3단계에서는 B-Tree가 48개 키까지 늘어남
  • 48개 아이템을 Factorio에서 수동으로 고르고 정렬하고 싶지 않아, 더 나은 값 표현 방식을 찾기 전까지 B-Tree는 비워 둠
  • BST와 B-Tree를 나란히 비교하고, YouTube 영상도 함께 둠

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 비효율적인 설계지만, Factorio에서 컴퓨터과학 이론을 구현한다는 건 필연적으로 최적이 아닌 방식으로 플레이한다는 뜻이기도 함
    Factorio는 B-Tree를 뽐내라고 만든 게임이 아니라, 도구들도 결국 Factorio를 플레이하도록 설계된 것임

    1. 2-3 트리, 레드-블랙 트리, B-Tree 같은 자가 균형 트리의 핵심은 단일 트리 구성 자체가 아니라 스스로 균형을 맞추는 부분인데, Factorio에서는 트리가 자기 자신을 재구성하도록 만들 수 없으니 가장 큰 특징이 빠져 있음
    2. 최적화 관점에서는 투입기가 벨트보다 느림. 벨트 하나당 투입기 4개를 써도 초당 약 12개밖에 못 옮기고, 파란 벨트는 초당 45개를 밀어낼 수 있음. 벨트만 쓰는 최적 설계라면 초당 45개로 동작하는 분배기를 써야 함
    3. 그래서 분배기와 컴퓨터과학이 만나는 지점은 Factorio의 분배기와 Benes 네트워크임. 2입력 2출력 크로스바만으로 만든 네트워크를 공부하려면 https://en.wikipedia.org/wiki/Clos_network부터 보면 됨. Benes 네트워크는 2입력 2출력 크기의 Clos 네트워크일 뿐이고, Clos 네트워크는 5대7 같은 임의 크기도 가능함
      Factorio에서 찾아볼 메타는 “혼합 벨트” 설계인 듯함
    • 더 구체적인 형태로는 하나의 벨트가 여러 재료를 균형 있게 싣고 자기 자신을 도는 스시 벨트가 있음
      어떤 설계는 정해진 비율로 새 아이템을 받아들이기만 하고, 어떤 설계는 흐트러졌을 때 실제로 다시 균형을 맞추기도 함. 개인적으로는 이게 가장 마음에 듦: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      이 예시는 게임 내 회로 논리를 쓰지만, Factorio 포럼에는 회로 없는 섹션도 있음: https://forums.factorio.com/viewforum.php?f=202
      재미있는 점은 Factorio의 “fish” 객체가 쓸모없는 농담 아이템인데, 아무 데도 쓰이지 않기 때문에 때로는 널 값, 벨트가 한 바퀴를 완료했다는 플래그, 디버깅 도구로 쓰인다는 것임: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • 컨베이어 벨트 위에 JSON을 올릴 수 있게 해주는 “Scriptorio” 같은 Factorio 확장이 있으면 어떨까 싶음. JavaScript나 Lua 함수 공장도 함께 쓰는 식임
      그러면 삽입·검색할 객체뿐 아니라 B-Tree 자체도 컨베이어 벨트와 투입기로 이동시킬 수 있음
      공장을 통과하는 컨베이어 벨트 루프로 재귀 검색 함수를 작성해서, 리프에 닿을 때까지 트리를 한 레벨씩 벗겨내며 돌리고 루프를 끊어 결과를 출력할 수도 있음
      표준 JavaScript라기보다는 데이터 흐름에 가까운 흥미로운 실행 모델임. 서로 다른 컨베이어 벨트, 투입기, 공장에서 같은 기반 JSON 객체를 여러 참조로 가리키게 해서 “양자 터널링”이나 “원격 작용”을 허용해야 할까? 유용할 수는 있지만, Factorio는 전통적으로 각 물리 아이템이 고유한 정체성을 가진다고 다루니 여러 참조를 지원하지 않는 편이 더 “현실적”일 수도 있음. 아니면 “Quantum Tunneling JSON” 기술을 연구한 뒤 “JSON Reference Entangler Factory”에서만 여러 참조를 만들 수 있게 할 수도 있음
    • Clos 네트워크 글을 대충 훑어보니, Factorio에서 그런 네트워크를 만들 수 있다면 여기 보이는 것 같은 단순한 신경망 설계도 가능해 보임: [1]
      특정 위치에 도착하는 자원 밀도에 가중치를 줘서 출력을 바꾸는 식도 가능할 듯함. 여기서 보이는 메커니즘 [2]을 보면 병합·분리와 세 가지 벨트 속도로 밀도 가중 의사결정을 만들 수 있을 것 같음
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • 다음에는 자가 균형까지 구현할 수 있는지 보고 싶음. 봇이 여기서 유용할 것 같다고 생각했는데, 봇이 설계도를 동적으로 건설하게 만들 수 있는지는 잘 모르겠음
    • 그래서 Factorio를 안 함. 그 정도 두뇌 자원은 인류를 위해 쓸 수 있고, 결과물을 보여주면 소셜 미디어 반응도 얻을 수 있음
      화면 속 숫자를 대가로 두뇌를 요구하는 게임은 내 목록 최하위임. 나는 뭔가 새로운 걸 배우고 싶음
      퍼즐 요소가 있을 수 있고 우리가 그걸 재미있다고 정할 수도 있지만, 공부도 재미있다고 정할 수 있지 않나 싶음

  • 멋진 작업임
    “Database Internals”를 북클럽에서 읽고 있고, 이번 주가 B-Tree를 다루는 2장이었다고 함
    참고로 신청은 닫혔지만, 원한다면 Database Internals를 구해서 여기 일정과 노트를 따라 “읽기 전용”으로 함께 볼 수 있음: https://eatonphil.com/2023-database-internals.html

  • “이진 검색 트리는 디스크 기반 저장소에 좋지 않다”는 이유들은 메모리 저장소에도 적용됨
    B-Tree 노드 하나를 검색하는 편이 이진 트리에서 같은 양의 포인터를 따라가는 것보다 빠름. 물론 구현 복잡도가 올라가지만, C를 쓰는 게 아니라면 보통 트리 기반 맵을 직접 구현하지는 않을 것임
    내부 노드에는 더 많은 항목을 넣고 값은 리프에만 저장하는 식의 변형도 가능함. 맵이 아니라 집합만 만드는 게 아니라면 말임. 여기에 이웃 노드까지 연결하면 사실상 건너뛰기 목록(skip list)에 가까워짐

  • 왜 하필 여기 Factorio 콘텐츠가 올라와서 또 100시간쯤 빠져들고 싶은 충동을 만들었는지 모르겠음. 올해도 이미 할 만한 좋은 게임이 너무 많음

    • 내년 말쯤 대규모 재조정과 Space Age 확장팩이 예정되어 있으니, 그때까지 기다리는 것도 괜찮을 수 있음

  • 이건 전부 분배기로도 할 수 있고, 상자나 필터 투입기는 필요 없을 것 같음. 설명은 좋음

    • 어떻게 하는지 모르겠음
      단순히 출력을 여러 줄로 나누려는 게 아님. 상자는 여기 2차원으로 배치된 B-Tree의 해당 “노드”에 저장된 아이템을 나타냄
      영상을 볼 시간은 없었지만, 글과 스크린샷을 보면 투입기에 관련 논리가 붙어 있어서 트리의 “정렬된” 성질을 유지하도록 아이템을 알맞은 자식 노드 경로로 보내는 구조임
      원글의 키 값 선택을 보면 분배기로 나누는 것도 가능하긴 하겠지만, 기억상 분배기는 필터를 하나만 받을 수 있어서 각 분기점마다 여러 개가 필요함. 그 분기점의 아이템 수만큼 필요하다는 뜻임. 필터 투입기는 여러 필터를 허용하니 여기서는 좀 더 낫고, 첫 스크린샷에서도 볼 수 있음
      물론 B-Tree 설계를 통째로 포기하고 n개의 분배기로 n개의 상자에 정렬할 수도 있겠지만, 그건 재미없고 원글이 의도한 것도 아닌 듯함
    • 각 투입기에 여러 아이템을 할당하고 있음
      분배기 필터는 한 가지 아이템만 한쪽으로 보내고 나머지는 다른 쪽으로 보냄. 하지만 이 예시는 여러 종류가 한쪽으로 가고, 여러 종류가 다른 쪽으로 가는 구조라서 다름
    • 여러 아이템을 정렬·필터링해야 함. 예를 들어 첫 노드에서는 나무, 석탄, 돌은 왼쪽으로 보내고 금속은 오른쪽으로 보내야 하는데, 분배기 필터는 아이템 하나만 필터링할 수 있음

  • Factorio가 그렇게 괜찮은 게임인지 궁금함. 다들 좋다고 하지만, 공장 짓기라는 주제가 좀 지루해 보이고 게임이 너무 반복적일까 걱정됨

    • 해보기 전에는 나도 꽤 회의적이었고 같은 걱정을 했음. 그런데 정신 차려보니 100시간 이상을 넣어버렸음
    • 내가 아는 Factorio 플레이어들은 전부 1,000시간 이상을 쏟았음

  • 정말 멋지지만, 글을 쓰려는 사람끼리 하는 말로는 문장 시작에 대문자를 쓰지 않는 게 꽤 산만하게 느껴짐

  • Factorio의 회로 시스템으로 구현할 줄 알았음

답변달기
GeekNews BeeBS 게시판 오픈! 자유로운 이야기와 소소한 일상을 함께 나눠보세요.