Hierarchical SQL in Django: Nested Set

개요

• 노드마다 숫자의 범위를 저장하고 숫자 범위가 다른 노드에 포함되는지 여부로 ascendant, descendant를 결정한다.
• 트리에 노드 추가/삭제시 모든 ascendant에 대해 값 수정이 필요하다.
• 하지만 트리에 대해 traversing하거나 조회하는 성능이 뛰어나다

Django Model Example

class NSNode(models.Model):
    left_number = models.PostiveIntegerField(db_index=True)
    right_number = models.PositiveIntegerField(db_index=True)
    ...

ORM Example

def get_descendants(node: NSNode) -> QuerySet:
    range_of_descendants = node.left + 1, node.right - 1
    descendant_queryset = NSNode.objects.filter(
    	left__range = range_of_descendants
    )
    
    return descendant_queryset

def get_ascendants(node: NSNode) -> QuerySet:
    ascendant_queryset = NSNode.objects.filter(
    	Q(left__lt=node.left) &
        Q(right_gt=node.right)
    )
    
    return ascendant_queryset