<div id="readability-page-1" class="page"><div> &nbsp;데이터베이스를 공부하는 방법 중에 하나는, 잘 구현된 라이브러리를 보고 어떤 구조로 데이터베이스를 설계했는지 보는 것이라고 생각합니다. 장고에서, 카데고리를 추가해야 할 일이 있었는데요. 저는 항상 하던 것과 같이 self Foreign key와 name만을 필드로 가지는 모델을 정의했습니다.

&nbsp;그런데, 찾다보니 mptt라는 것이 있었는데요. 간단하게 소개해 드리겠습니다.

<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style3">
&nbsp;먼저 계층형 쿼리에 대한 것부터 알아야 하는데요. 흔히 댓글, 대댓글이라던지 1차, 2차, 3차 카데고리와 같은 것들이 계층형 구조라고 할 수 있어요. 여기서 질문을 하나 던져볼게요. 대분류가 Game에 속하는 글은 어떤 것인가? 예를 들자면, 저는 btd5에 대해 썼는데요. btd5의 대분류 역시 Game입니다. 그러면 btd5는 Game의 자식이라 할 수 있는데요. 제가 쓴 글이 btd5에 대해서 쓴 것을 알아맞추기는 쉽습니다만, Game에 대해 썼다는 것은 어떻게 알아내야 할까요?


<figure data-origin-width="435" data-origin-height="274" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/BGe1j/btrFwufIjR0/dfyScRV3tH9njTBIhAsUSK/img.png" data-filename="mp8.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;이러한 구조를 설계할 때 먼저 고려해 볼만한 것은 MPTT입니다. 결론부터 말하자면, 카데고리 분류는 insert, delete가 많이 될 일이 거의 없습니다. 대신, 조회연산이 상대적으로 매우 많이 일어납니다. 따라서, 이 모델을 쓰기에 적합한데요. 어떻게 동작하는지 admin page에 찍어본 다음에 이야기 해 보도록 하겠습니다.

&nbsp;먼저, order_insertion_by를 "name"으로 했는데요. 이에 대한 건 밑에서 계속 후술하겠습니다.


<figure data-origin-width="629" data-origin-height="128" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/22Ctd/btrFuDSggs4/wZqTX9JTomihnwcAf5THS1/img.png" data-filename="mp1.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;먼저, 대분류 Game을 추가했습니다. LFT가 1이고 RGHT가 2이고, TREE ID가 1이라는 정보가 추가되었습니다.


<figure data-origin-width="648" data-origin-height="154" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/pfuXE/btrFvVEEgei/9yP2XBY3YXIYe5gdnTeZLK/img.png" data-filename="mp2.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;다음에 또 대분류 IT를 추가했습니다. LFT가 1이고 RGHT가 2이고, TREE ID가 2인데요. 왜 GAME하고 IT하고 LFT 값과 RGHT 값이 같을까요? 당연한 이야기겠지만, Game을 루트로 가지는 트리, IT를 루트로 가지는 트리가 있기 때문입니다. 이를 그림으로 나타내면 아래와 같습니다.


<figure data-origin-width="284" data-origin-height="123" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/cAKWUI/btrFt8ZxO2s/b9zSN2SvgPtX9kazzB59K1/img.png" data-filename="mp9.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;포레스트같이 생겼네요. 나무 여러개가 모여있으니까요. 이제 Game 밑에 rpg를 추가해 봅시다.


<figure data-origin-width="659" data-origin-height="191" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/28AQy/btrFvq5XlNc/b29bPlFzjzkIY8yr9TiHg0/img.png" data-filename="mp3.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그러면 어떤 일이 일어나는가? rpg의 LFT, RGHT가 2, 3이 되고, Game의 RGHT가 4가 됨을 볼 수 있어요. 이게 뭔 말인지 잘 모르겠네요. 트리를 다시 그려보면서 이야기를 해 봅시다.


<figure data-origin-width="288" data-origin-height="261" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/bO9x1c/btrFxiTEcIK/851QkTx2w2YKJmzsgxXmPK/img.png" data-filename="mp10.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그림을 그려보니, 요래 그려짐을 알 수 있어요. 아직 무슨 규칙인지 잘 모르겠으니, Game 밑에 defense라는 카데고리를 하나 더 추가해 봅시다.


<figure data-origin-width="657" data-origin-height="223" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/Ku7Lq/btrFuoueyQo/FBXKSulsq2Gk36vipvRIAK/img.png" data-filename="mp4.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그러면 결과가 이렇게 나옵니다. 이 상태를 그려 봅시다.


<figure data-origin-width="370" data-origin-height="263" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/84uFc/btrFtPlCmai/c1cIsJF2EnW65u0KErO78K/img.png" data-filename="mp11.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;어? 이번에는 어떤가요? 뭔가 규칙이 보이셨나요? 전위 순회와 관련이 매우 깊다는 것을 알 수 있어요. 이제 rpg 밑에 maple을 추가해 보겠습니다.


<figure data-origin-width="653" data-origin-height="241" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/dWUVNQ/btrFv0Mt4Q8/mPP9rMbVSqrJEUumyiLJYK/img.png" data-filename="mp5.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그러면, defense는 변하지 않았는데, rpg, maple, Game의 메타 데이터가 변경되었음을 알 수 있습니다.

<figure data-origin-width="351" data-origin-height="391" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/d74RMc/btrFwuNz6pG/PJyeoQF7d0IPICTfGzupPk/img.png" data-filename="mp12.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;감이 오시나요? LFT는 root인 경우 1입니다. x의 자식인 경우, 1번째 자식일 때에는 x의 LFT값에 1을 더한 값이고, 그렇지 않다면, 이전 자식의 RGHT + 1 값임을 알 수 있습니다. RGHT 값은 어떨까요? 자식이 없다면, LFT에 1을 더한 값이고, 있다면 가장 마지막 자식의 RGHT 값에 1을 더한 값입니다.


<figure data-origin-width="668" data-origin-height="259" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/m37N6/btrFvVLnpCO/FcbIeoLnsQAi2zcIHsjhM1/img.png" data-filename="mp6.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;이제, defense 밑에 btd5를 추가해 보면, 이 규칙이 딱 떨어지는 것을 알 수 있습니다. 여기까지 보셨다면 대략 눈치채셨겠지만, 트리를 구간으로 펴는 트릭과 비슷하다는 것을 알 수 있습니다. 그도 그럴 것이, 계층형 쿼리에서 가장 많이 나오는 부분은, 정렬하는 부분과 A가 B의 부모, 혹은 자식인가? 이기 때문입니다.

&nbsp;이제, defense를 삭제한 다음에, Category의 상태를 봅시다.


<figure data-origin-width="631" data-origin-height="189" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/s1Lot/btrFvXh9Xx4/KDWhKbn9ryGiu8PWa9hUW1/img.png" data-filename="mp7.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그러면, 요래 변경되었음을 알 수 있습니다. 중요한 것은 데이터를 추가, 삭제할 때 마다, 레코드가 n개 있다면 최악의 경우에 n개의 레코드를 업데이트 해야 합니다. 구간 관련 데이터를 업데이트 해야 하기 때문입니다. 다시 말해, insert와 삭제가 매우 극단적으로 적게 일어나는 경우라면 매우 매력적인 도구가 될 수 있음을 의미합니다.


<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style3">
&nbsp;두 가지 질문에 대한 답을 해 봅시다. 먼저, 정렬. 어떻게 하면 될까요? 먼저 대분류를 보면 TREE ID라고 되어 있는데요. 이것은 루트의 고유 ID 정도라고 생각하셔도 좋습니다. 그러니, 이것을 기준으로 1차 정렬이 되어야 할 거고요. 2차 기준은 무엇일까요?


<figure data-origin-width="224" data-origin-height="390" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/AghTG/btrFt9jO9mr/229lbUUZGx1bwZqxwfAKH0/img.png" data-filename="mp13.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;LFT일 겁니다. 왜냐하면 LFT는 최초 방문한 시점과 관련된 변수이기 때문입니다. 전위 순회에서, root, L, R 순으로 방문하게 되는데요. 부모가 같다면 최근에 생성된 데이터를 나중에 방문할 겁니다. 그리고, 부모보다는 자식을 더 늦게 방문할 겁니다. 당장, 위 그림에 있는 LFT도 이를 만족함을 알 수 있습니다.

&nbsp;이제, maple이 GAME 카데고리인지 어떻게 판별하면 좋을까요? 이것도 복잡하지 않습니다. LFT와 RGHT를 트리에서의 구간 LFT ~ RGHT를 커버한다고 생각해 봅시다.


<figure data-origin-width="232" data-origin-height="403" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/bt7BmA/btrFvVEFXD8/iW0uSsUALw4wl9VN2zdkIk/img.png" data-filename="mp14.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;그러면, 카데고리 A가 구간 x1 ~ y1을 커버하고, 카데고리 B가 구간 x2 ~ y2를 커버한다 했을 때 구간 x1 ~ y1에 구간 x2 ~ y2가 속하면, A가 B의 부모입니다. 예를 들어 GAME은 1 ~ 8을 커버하고, maple은 5 ~ 6을 커버하기 때문에, GAME은 maple의 부모입니다. 반대로, 카데고리 A가 구간 x1 ~ y1에, 카데고리 B가 구간 x2 ~ y2에 속한다면, A는 B의 자식입니다. 만약에 구간 둘의 교집합이 없으면 어떨까요?


<figure data-origin-width="230" data-origin-height="397" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/cvnHQk/btrFwveEP9a/HCky1KEtWnn2dfK5N4ouQ0/img.png" data-filename="mp15.png" data-ke-mobilestyle="alignCenter"></figure>
&nbsp;이 경우, defense는 maple이 아니고, maple 또한 def가 아닙니다. 둘 다 별개라는 의미입니다. </div></div>

강아지의 코딩공부

데이터베이스를 공부하는 방법 중에 하나는, 잘 구현된 라이브러리를 보고 어떤 구조로 데이터베이스를 설계했는지 보는 것이라고 생각합니다. 장고에서, 카데고리를 추가해야 할 일이 있었는데요. 저는 항상 하던 것과 같이 self Foreign key와 name만을 필드로 가지는 모델을 정의했습니다.
 
 그런데, 찾다보니 mptt라는 것이 있었는데요. 간단하게 소개해 드리겠습니다.
 
 먼저 계층형 쿼리에 대한 것부터 알아야 하는데요. 흔히 댓글, 대댓글이라던지 1차, 2차, 3차 카데고리와 같은 것들이 계층형 구조라고 할 수 있어요. 여기서 질문을 하나 던져볼게요. 대분류가 Game에 속하는 글은 어떤 것인가? 예를 들자면, 저는 btd5에 대해 썼는데요. btd5의 대분류 역시 Game입니다. 그러면 btd5는 Game의 자식이라 할 수 있는데요. 제가 쓴 글이 btd5에 대해서 쓴 것을 알아맞추기는 쉽습니다만, Game에 대해 썼다는 것은 어떻게 알아내야 할까요?
 
 
 이러한 구조를 설계할 때 먼저 고려해 볼만한 것은 MPTT입니다. 결론부터 말하자면, 카데고리 분류는 insert, delete가 많이 될 일이 거의 없습니다. 대신, 조회연산이 상대적으로 매우 많이 일어납니다. 따라서, 이 모델을 쓰기에 적합한데요. 어떻게 동작하는지 admin page에 찍어본 다음에 이야기 해 보도록 하겠습니다.
 
 먼저, order_insertion_by를 "name"으로 했는데요. 이에 대한 건 밑에서 계속 후술하겠습니다.
 
 
 먼저, 대분류 Game을 추가했습니다. LFT가 1이고 RGHT가 2이고, TREE ID가 1이라는 정보가 추가되었습니다.
 
 
 다음에 또 대분류 IT를 추가했습니다. LFT가 1이고 RGHT가 2이고, TREE ID가 2인데요. 왜 GAME하고 IT하고 LFT 값과 RGHT 값이 같을까요? 당연한 이야기겠지만, Game을 루트로 가지는 트리, IT를 루트로 가지는 트리가 있기 때문입니다. 이를 그림으로 나타내면 아래와 같습니다.
 
 
 포레스트같이 생겼네요. 나무 여러개가 모여있으니까요. 이제 Game 밑에 rpg를 추가해 봅시다.
 
 
 그러면 어떤 일이 일어나는가? rpg의 LFT, RGHT가 2, 3이 되고, Game의 RGHT가 4가 됨을 볼 수 있어요. 이게 뭔 말인지 잘 모르겠네요. 트리를 다시 그려보면서 이야기를 해 봅시다.
 
 
 그림을 그려보니, 요래 그려짐을 알 수 있어요. 아직 무슨 규칙인지 잘 모르겠으니, Game 밑에 defense라는 카데고리를 하나 더 추가해 봅시다.
 
 
 그러면 결과가 이렇게 나옵니다. 이 상태를 그려 봅시다.
 
 
 어? 이번에는 어떤가요? 뭔가 규칙이 보이셨나요? 전위 순회와 관련이 매우 깊다는 것을 알 수 있어요. 이제 rpg 밑에 maple을 추가해 보겠습니다.
 
 
 그러면, defense는 변하지 않았는데, rpg, maple, Game의 메타 데이터가 변경되었음을 알 수 있습니다.
 
 감이 오시나요? LFT는 root인 경우 1입니다. x의 자식인 경우, 1번째 자식일 때에는 x의 LFT값에 1을 더한 값이고, 그렇지 않다면, 이전 자식의 RGHT + 1 값임을 알 수 있습니다. RGHT 값은 어떨까요? 자식이 없다면, LFT에 1을 더한 값이고, 있다면 가장 마지막 자식의 RGHT 값에 1을 더한 값입니다.
 
 
 이제, defense 밑에 btd5를 추가해 보면, 이 규칙이 딱 떨어지는 것을 알 수 있습니다. 여기까지 보셨다면 대략 눈치채셨겠지만, 트리를 구간으로 펴는 트릭과 비슷하다는 것을 알 수 있습니다. 그도 그럴 것이, 계층형 쿼리에서 가장 많이 나오는 부분은, 정렬하는 부분과 A가 B의 부모, 혹은 자식인가? 이기 때문입니다.
 
 이제, defense를 삭제한 다음에, Category의 상태를 봅시다.
 
 
 그러면, 요래 변경되었음을 알 수 있습니다. 중요한 것은 데이터를 추가, 삭제할 때 마다, 레코드가 n개 있다면 최악의 경우에 n개의 레코드를 업데이트 해야 합니다. 구간 관련 데이터를 업데이트 해야 하기 때문입니다. 다시 말해, insert와 삭제가 매우 극단적으로 적게 일어나는 경우라면 매우 매력적인 도구가 될 수 있음을 의미합니다.
 
 
 두 가지 질문에 대한 답을 해 봅시다. 먼저, 정렬. 어떻게 하면 될까요? 먼저 대분류를 보면 TREE ID라고 되어 있는데요. 이것은 루트의 고유 ID 정도라고 생각하셔도 좋습니다. 그러니, 이것을 기준으로 1차 정렬이 되어야 할 거고요. 2차 기준은 무엇일까요?
 
 
 LFT일 겁니다. 왜냐하면 LFT는 최초 방문한 시점과 관련된 변수이기 때문입니다. 전위 순회에서, root, L, R 순으로 방문하게 되는데요. 부모가 같다면 최근에 생성된 데이터를 나중에 방문할 겁니다. 그리고, 부모보다는 자식을 더 늦게 방문할 겁니다. 당장, 위 그림에 있는 LFT도 이를 만족함을 알 수 있습니다.
 
 이제, maple이 GAME 카데고리인지 어떻게 판별하면 좋을까요? 이것도 복잡하지 않습니다. LFT와 RGHT를 트리에서의 구간 LFT ~ RGHT를 커버한다고 생각해 봅시다.
 
 
 그러면, 카데고리 A가 구간 x1 ~ y1을 커버하고, 카데고리 B가 구간 x2 ~ y2를 커버한다 했을 때 구간 x1 ~ y1에 구간 x2 ~ y2가 속하면, A가 B의 부모입니다. 예를 들어 GAME은 1 ~ 8을 커버하고, maple은 5 ~ 6을 커버하기 때문에, GAME은 maple의 부모입니다. 반대로, 카데고리 A가 구간 x1 ~ y1에, 카데고리 B가 구간 x2 ~ y2에 속한다면, A는 B의 자식입니다. 만약에 구간 둘의 교집합이 없으면 어떨까요?
 
 
 이 경우, defense는 maple이 아니고, maple 또한 def가 아닙니다. 둘 다 별개라는 의미입니다.

django mptt와 업뎃이 별로 없는 계층형 구조에 대해 알아봅시다.

댓글