· 개발

Linux 커널 rbtree: 비교 함수를 저장하지 않고 노드를 구조체에 넣어 쓰는 레드-블랙 트리

Linux의 레드-블랙 트리는 비교 함수를 저장하지 않습니다. 노드를 구조체에 넣는 방식, 직접 쓰는 검색·삽입 루프와 호출마다 비교 함수를 받는 도우미, 색 비트, cached·augmented 트리, 락 없는 조회의 한계를 v6.17 소스로 정리했습니다.

개발알고리즘자료구조Linux

Linux 커널의 레드-블랙 트리에는 rb_insert(tree, key, value) 같은 함수가 없습니다. 트리가 비교 함수를 등록받아 저장해 두는 곳도 없습니다. 기본 API에서는 트리를 내려가며 왼쪽으로 갈지 오른쪽으로 갈지 정하는 루프를 사용하는 쪽이 직접 쓰고, 라이브러리는 그 끝에서 색을 바꾸고 회전하는 일만 맡습니다. v6.17 헤더에는 이 루프를 대신 돌려 주는 인라인 도우미도 있지만, 이들도 비교 함수를 저장하지 않고 호출할 때마다 인자로 받습니다.

교과서의 레드-블랙 트리와 같은 자료구조인데 API 모양이 이렇게 다른 이유와, 그 모양 때문에 생기는 선택지를 정리합니다. 기준은 Linux v6.17의 Documentation/core-api/rbtree.rst, include/linux/rbtree.h, include/linux/rbtree_augmented.h, lib/rbtree.c입니다.

콜백을 빼고 루프를 넘긴 이유

커널 문서는 이 구현이 속도에 맞춰져 있다고 설명합니다. 노드와 데이터를 따로 두고 포인터로 잇는 대신 struct rb_node를 데이터 구조체 안에 넣기 때문에 간접 참조가 한 단계 적고 캐시 지역성이 좋다는 것입니다. 트리가 비교 콜백 함수 포인터를 들고 있다가 부르는 대신 사용자가 검색·삽입 함수를 직접 쓰게 한 것도 같은 이유입니다. Andrea Arcangeli의 1999년 저작권 표시가 붙은 rbtree.h 머리 주석은 콜백을 쓰면 성능이 크게 떨어지니 C에서 성능과 범용성을 함께 얻으려면 이렇게 할 수밖에 없다고 적었습니다. 잠금도 사용자 몫입니다.

문서는 이 트리를 다른 커널 자료구조와도 비교합니다. 해시 테이블은 정렬 상태로 유지되지 않아 순서대로 훑기 어렵고, 특정 크기와 해시 함수에 맞춰 조정해야 합니다. rbtree는 임의의 키를 저장하면서 규모가 커져도 무난하게 동작한다고 적었습니다. 해시 테이블이 최악의 경우 어떻게 되는지는 해시 테이블의 최악 시간 복잡도 글에서 다뤘습니다.

노드는 데이터 안에 있다

트리에 넣을 구조체는 struct rb_node 멤버를 가집니다.

struct mytype {
	struct rb_node node;
	char *keystring;
};

struct rb_root mytree = RB_ROOT;

트리 함수는 struct rb_node *만 주고받습니다. 여기서 바깥 구조체를 얻을 때는 container_of()나 같은 일을 하는 rb_entry(node, type, member) 매크로를 씁니다. 키가 어디에 있고 어떤 타입인지는 트리가 전혀 모릅니다.

검색은 루트에서 시작해 비교 결과에 따라 rb_left나 rb_right를 따라가는 평범한 이진 탐색 트리 검색입니다. 문서의 예제도 strcmp 결과로 방향을 정하는 while 루프 하나입니다.

삽입은 두 단계로 나뉜다

삽입은 새 노드를 매달 자리를 찾는 일과, 매단 뒤 균형을 맞추는 일로 나뉩니다. 문서의 예제가 하는 일을 의사코드로 옮기면 이렇습니다.

link   = 루트 링크의 주소          (struct rb_node ** 타입)
parent = 없음
link가 가리키는 노드 cur가 있는 동안:
    parent = cur
    새 키 < cur의 키  →  link = cur의 왼쪽 링크 주소
    새 키 > cur의 키  →  link = cur의 오른쪽 링크 주소
    같으면            →  실패 반환 (같은 키가 이미 있음)

1단계: rb_link_node(새 노드, parent, link)   빈 자리에 매달기
2단계: rb_insert_color(새 노드, root)        색 고치기와 회전

문서의 C 예제에서는 container_of()로 cur의 바깥 구조체를 얻고 strcmp로 키를 비교합니다. 검색과 다른 점은 노드가 아니라 노드를 가리키는 포인터의 주소(struct rb_node **)를 따라간다는 것입니다. 루프가 끝나면 link는 새 노드를 써 넣을 빈 자리입니다. rb_link_node()는 새 노드의 부모를 기록하고 두 자식을 NULL로 둔 뒤 그 자리에 새 노드를 씁니다. 그다음 rb_insert_color()가 색을 고치고 필요하면 회전합니다.

같은 키를 만났을 때 무엇을 할지도 이 루프가 정합니다. 위 예제는 실패를 돌려주지만, 중복을 허용하고 싶으면 한쪽으로 계속 내려가게 쓰면 됩니다.

v6.17 헤더에 있는 도우미 함수

문서의 예제처럼 매번 루프를 쓰지 않아도 되도록, v6.17의 rbtree.h에는 비교 함수를 호출마다 인자로 받는 도우미가 들어 있습니다. 트리에 비교 함수가 저장되는 것은 아니므로, 같은 트리에는 매번 일관된 비교 함수를 넘겨야 합니다. 아래 표에서 rb_for_each()만 for 루프로 펼쳐지는 전처리기 매크로이고, 나머지는 static __always_inline 함수입니다.

이름 형태 비교 인자 하는 일
rb_add() 인라인 함수 less(a, b) 노드를 넣습니다. 반환값 없음
rb_find_add() 인라인 함수 cmp(a, b) cmp가 0인 노드가 있으면 그 노드를 돌려주고, 없으면 넣고 NULL을 돌려줍니다
rb_find() 인라인 함수 cmp(key, node) 키와 일치하는 노드나 NULL
rb_find_first() 인라인 함수 cmp(key, node) 일치하는 노드 중 가장 왼쪽 것
rb_for_each() 매크로 cmp(key, node) 일치하는 노드를 차례로 순회 (rb_find_first()와 rb_next_match() 사용)

헤더 주석은 두 연산자의 관계를 cmp(a->key, b) < 0이 less(a, b)와 같다는 식으로 정의합니다. 이 연산자가 부분 순서만 정의하면 rb_find()가 일치하는 원소 중 어느 것을 찾을지는 보장하지 않는다고 적었습니다. 검색용 키만 넘기는 이런 형태를 둔 이유로는, 비교를 위해 스택에 가짜 객체를 만들 필요가 없게 하려는 것이라고 설명합니다. 객체가 크면 그게 어려울 수 있기 때문입니다.

rb_add()의 루프를 보면 less(node, parent)가 참일 때만 왼쪽으로 가고, 같으면 오른쪽으로 갑니다. 여기서 끌어낼 수 있는 성질이 있습니다(코드에서 추론한 것이고 주석에 적힌 보장은 아닙니다). 트리 전체를 rb_add()와 일관된 less로 만들었다면, 새 노드는 같은 키를 가진 기존 노드들보다 정렬 순서상 뒤에 놓입니다. 회전은 정렬 순서를 바꾸지 않으므로 이 순서는 유지됩니다. 같은 키의 첫 번째 원소를 찾을 때는 rb_find()가 아니라 rb_find_first()를 써야 하는 것도 같은 맥락입니다.

색은 부모 포인터의 하위 비트에 들어 있다

rb_node에는 색을 위한 별도 필드가 보이지 않습니다. rbtree.h와 rbtree_augmented.h의 매크로를 보면 부모 포인터와 색이 __rb_parent_color라는 unsigned long 하나에 함께 들어 있습니다.

__rb_parent_color (unsigned long 하나)
[ 부모 노드 주소 ...... | b1 | b0 ]   b1, b0 = 하위 2비트
rb_parent(r) = 값 & ~3   하위 2비트를 지워 부모 주소를 얻음
rb_color(r)  = 값 & 1    비트 0이 색 (RB_RED = 0, RB_BLACK = 1)

이 방식은 노드 주소의 하위 2비트가 항상 0이라는 전제 위에서만 성립합니다. 그 정렬을 보장하는 struct rb_node 정의는 rbtree_types.h에 있는데, 이 글을 쓰면서 확인한 파일에는 포함되지 않았습니다.

같은 필드는 “트리에 들어 있지 않은 노드”를 표시하는 데도 쓰입니다. RB_CLEAR_NODE(node)는 이 값을 노드 자신의 주소로 채우고, RB_EMPTY_NODE(node)는 그 상태인지 검사합니다. rb_next()와 rb_prev()는 이런 노드를 받으면 NULL을 돌려줍니다.

균형과 회전 횟수

lib/rbtree.c 머리 주석은 레드-블랙 트리의 다섯 가지 성질을 적고, 그중 “빨간 노드의 두 자식은 모두 검정”과 “루트에서 잎까지의 모든 단순 경로에 검정 노드 수가 같다”가 O(log n)을 보장한다고 설명합니다. 빨간 노드가 연달아 올 수 없으니, 모든 경로의 검정 노드 수를 B라 하면 가장 긴 경로는 2B라는 논리입니다.

커널 문서는 AVL 트리와 비교해 삽입과 삭제에서 실시간 최악 성능이 더 좋다고 하며, 균형을 맞추는 데 삽입은 회전이 최대 2번, 삭제는 최대 3번이라고 적었습니다. 대신 조회는 조금 느리지만 여전히 O(log n)이라고 합니다.

__rb_insert()의 구조를 보면 이 숫자가 어디서 나오는지 보입니다.

삽입 경우 조건 처리 회전 이후
Case 1 삼촌이 빨강 부모와 삼촌을 검정, 조부모를 빨강으로 0 조부모에서 다시 반복
Case 2 삼촌이 검정, 노드가 안쪽 자식 부모에서 회전해 Case 3 모양으로 1 Case 3으로 이어짐
Case 3 삼촌이 검정, 노드가 바깥쪽 자식 조부모에서 회전 1 종료

회전하는 경우는 Case 3에서 반드시 끝나므로 회전은 최대 2번입니다. 다만 Case 1은 색만 바꾸고 두 단계 위에서 루프를 다시 돌기 때문에, 색 바꾸기는 루트 쪽으로 여러 번 올라갈 수 있습니다. “회전 최대 2번”이 “삽입 후 작업이 상수 시간”이라는 뜻은 아닙니다. 삭제 쪽 ____rb_erase_color()도 같은 구조로, 회전하는 경우(1, 3, 4)를 다 거쳐도 Case 4에서 끝나고, 색만 바꾸는 Case 2는 부모 쪽으로 올라갈 수 있습니다.

순회: 스택 없이 부모 포인터로

정렬 순서로 훑는 함수는 rb_first(), rb_last(), rb_next(), rb_prev() 네 개입니다.

struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

rb_next()는 오른쪽 자식이 있으면 그 아래로 내려가 가장 왼쪽 노드를 찾고, 없으면 부모 포인터를 따라 올라가다가 처음으로 왼쪽 자식 자리에서 올라온 부모를 돌려줍니다. 별도의 스택이 필요 없는 것은 노드마다 부모 포인터가 있기 때문입니다.

트리를 통째로 해제할 때는 후위 순회가 있습니다. rbtree_postorder_for_each_entry_safe(pos, n, root, field)는 자식을 부모보다 먼저 방문하고, 다음 노드를 미리 받아 두므로 루프 본문에서 pos의 메모리를 해제해도 됩니다. 주석은 여기에 단서를 답니다. 트리를 재배치하는 수정은 처리하지 못하며, pos에 rb_erase()를 호출하는 것도 여기에 해당합니다. 지우면서 균형을 다시 맞추면 일부 노드를 건너뛸 수 있기 때문입니다.

cached 트리: 가장 왼쪽 노드를 따로 들고 있기

rb_first()는 루트에서 왼쪽 끝까지 내려가므로 트리 높이만큼 걸립니다. 가장 작은 원소를 자주 찾는 쓰임새를 위해 struct rb_root_cached가 있습니다. 문서 설명으로는 일반 rb_root에 가장 왼쪽 노드를 가리키는 포인터 하나를 더한 것이고, 유지 비용은 무시할 만하지만 메모리를 더 씁니다. 헤더에서 rb_first_cached()는 그 포인터를 읽기만 하며 주석에도 “Same as rb_first(), but O(1)“이라고 적혀 있습니다.

캐시를 맞게 유지하는 책임은 일부 사용자에게 있습니다. rb_insert_color_cached(node, root, leftmost)는 새 노드가 가장 왼쪽인지를 세 번째 인자로 받습니다. 직접 쓴 삽입 루프에서 한 번이라도 오른쪽으로 갔다면 false를 넘겨야 합니다. rb_add_cached()는 이 판단을 대신 해 주고, 새 노드가 가장 왼쪽이 되면 그 노드를, 아니면 NULL을 돌려줍니다. 지울 때는 rb_erase_cached()가 지우는 노드가 가장 왼쪽이면 rb_next()로 캐시를 옮깁니다.

가장 작은 원소를 반복해서 꺼내는 일은 우선순위 큐의 일이기도 합니다. 힙이 전체 정렬 대신 무엇을 지키는지는 힙은 정렬된 배열이 아니다에서 다뤘습니다. rbtree는 전체를 정렬 상태로 두므로 위의 순회 함수로 어느 노드에서든 앞뒤 원소로 이동할 수 있습니다.

augmented 트리: 서브트리 요약값 유지하기

augmented rbtree는 각 노드에 추가 데이터를 두는데, 그 값은 그 노드를 루트로 하는 서브트리 전체의 함수여야 합니다. 문서의 예는 구간 트리입니다. 노드마다 구간 [start, last]를 저장하고, 서브트리 안에서 가장 큰 last를 __subtree_last로 둡니다. 왼쪽 자식의 이 값이 찾는 구간의 시작보다 작으면 왼쪽 서브트리에는 겹치는 구간이 없으니 내려갈 필요가 없습니다. 문서는 이렇게 가장 낮은 시작 주소의 일치 구간을 O(log n)에 찾는다고 설명합니다.

회전이나 삭제로 서브트리 모양이 바뀌면 요약값도 고쳐야 합니다. 그래서 사용자는 struct rb_augment_callbacks로 콜백 세 개를 넘깁니다.

  • propagate: 주어진 노드에서 지정한 멈춤 지점(또는 루트)까지 올라가며 값을 다시 계산합니다.
  • copy: 한 서브트리의 값을 새로 그 자리의 루트가 된 노드에 복사합니다.
  • rotate: copy와 같은 복사를 한 뒤, 이전 서브트리 루트의 값을 다시 계산합니다.

삽입할 때는 내려가는 경로의 값을 사용자가 먼저 갱신하고 rb_link_node() 뒤에 rb_insert_color() 대신 rb_insert_augmented()를 부릅니다. 삭제는 rb_erase_augmented()를 씁니다. 문서와 RB_DECLARE_CALLBACKS_MAX 매크로의 propagate는 다시 계산한 값이 원래 값과 같으면 거기서 멈춥니다. 그보다 위쪽 조상의 값은 바뀔 이유가 없기 때문입니다.

문서는 두 가지를 더 당부합니다. rb_erase_augmented()는 컴파일된 코드에 propagate와 copy 콜백이 인라인되어 함수가 커질 수 있으니, 사용자마다 호출 지점을 한 곳으로 두라고 합니다. 또 <linux/rbtree_augmented.h>는 구현 세부를 드러내므로 C 파일에서만 include하고 헤더 파일에서는 include하지 말라고 합니다. 헤더 자체의 주석도 공개 인터페이스는 콜백 구조체와 rb_insert_augmented(), rb_erase_augmented()의 프로토타입뿐이고 나머지는 의존하면 안 되는 구현 세부라고 밝힙니다.

락 없는 조회가 약속하는 것과 약속하지 않는 것

잠금은 사용자 몫이라고 했지만, lib/rbtree.c에는 락 없이 조회하는 경우를 위한 설명이 있습니다. 트리 구조를 바꾸는 저장(rb_left, rb_right)은 모두 WRITE_ONCE()로 하고, 프로그램 순서상 일시적으로라도 고리가 생기지 않게 합니다. 이 두 조건으로 보장되는 것은 이렇습니다.

  • 락 없는 순회는 유효한 원소만 보고, 고리에 갇히지 않고 끝납니다.
  • 조회가 원소를 돌려줬다면 그 원소는 맞는 원소입니다.

보장되지 않는 것도 적혀 있습니다. 회전은 원자적이지 않아서 조회가 서브트리 전체를 놓칠 수 있습니다. 원소를 돌려주지 않았다고 해서 그 원소가 없다는 뜻은 아닙니다. rb_find_rcu()의 주석도 동시 회전 중의 하강은 건전하지 않아 거짓 음성이 나올 수 있다고 경고합니다. 따라서 락 없이 찾은 “없음”은 그대로 결론으로 쓰면 안 되고, 확인이 필요하면 별도의 장치를 써야 합니다.

삽입 쪽에는 rb_link_node_rcu()와 이를 쓰는 rb_find_add_rcu()가 있습니다. 새 노드를 자리에 써 넣을 때 rcu_assign_pointer()를 쓰는 것이 일반 버전과의 차이입니다. 주석은 이를 “Store-Release”를 더한다고 표현합니다.

노드 바꾸기는 정렬을 다시 하지 않는다

rb_replace_node(old, new, root)는 지우고 다시 넣는 과정 없이 노드 하나를 바꿔 끼웁니다. 구현은 old의 포인터와 색을 new에 그대로 복사하고, 자식과 부모가 new를 가리키게 고칩니다. 비교는 한 번도 하지 않습니다. 그래서 문서는 새 노드의 키가 옛 노드와 다르면 트리가 망가질 가능성이 높다고 경고합니다. 키를 바꾸려면 지우고 다시 넣어야 합니다.

참고한 문서와 소스

문서와 소스는 2026년 10월 15일에 확인했습니다. 다른 커널 버전에서는 도우미 함수의 목록과 시그니처가 다를 수 있습니다.

블로그로