Radix Tree

Original Source: http://timewizhan.tistory.com/entry/%EB%9D%BC%EB%94%95%EC%8A%A4-%ED%8A%B8%EB%A6%ACRadix-Tree

Radix Tree

라딕스 트리(Radix Tree)란 무엇일까? .. 라딕스 트리에 대해 알아 보기 전에.!! 라딕스 트리는 왜 사용하는 것일까?? 간단히 말해서 페이지 캐시를 위해 쓰이는 자료 구조이다.

그러면 자세히 알아볼까?? 페이지를 좀 더 빠르게 이용하기 위해서 보통 캐시 기법을 사용한다. 그래서 디스크에서 페이지 인덱스가 주어지면 커널은 페이지 캐시를 찾기 위해 라딕스 트리를 이용한다. 왜냐하면!! 라딕스 트리에 페이지 캐시가 위치가 나오기 때문에.. 
아무튼. 커널은 라딕스 트리를 이용하여 있다면. 페이지 디스크립터를 가져오게 된다.~~
그리고 이 페이지 디스크립터를 보고 이 페이지가 어떤 페이지구나~ 라는 것을 알게 된다.

그렇기 떄문에.~ 페이지 캐시를 위해서는 라딕스 트리를 사용하는 것이다. 그러면 라딕스 트리의 구조에 대해 알아 볼까?? 잠시 '리눅스 커널의 이해'의 그림을 참조 하자면...

이렇게 일반적인 리스트(?) 와 같은 형태이다. root->node->node ... 형태로..그렇다면 자료 형태를 보도록 해보자.

height : 현재 트리의 높이
gfp_mask : 새로운 노드를 위해 메모리 요청이 있을 경우 사용하는 플래그
rnode : 1 단계에 있는 노드를 가르킴 (한 단계씩 내려감)

height : 현재 높이
count : 노드 내에 NULL이 아닌 포인터의 수
slot : 64개의 포인터 배열
RADIX_TREE_MAP_SIZE = 1UL << RADIX_TREE_MAP_SHIFT(6) ---> 그래서 2의 6승 = 64
tags : 좀 더 뒤에서..간단한 풀이할 개념이..ㅜㅜ

아무튼 각 노드당 64개의 페이지의 포인터를 가지고 있기 때문에 트리가 2개일 경우에는 2^6 * 2^6 = 2^12 -1
즉, 4096 - 1 -> 4095개의 페이지의 포인터를 가질 수 있다.

그렇다면 라딕스 트리를 이용해서 페이지를 어떻게 쉽게 찾을 수 있을까???
바로 리눅스 페이징 시스템 개념을 다시 한번 쓰는 것이다. (페이지 32 비트 , 48 비트를 비트 별로 쪼개는 것.)

페이지 인덱스가 들어오면 비트 별로 쪼개는 것이다.
라딕스 트리가 1이라면 하위 6 비트로 slot 배열 인덱스로.
2라면 하위 12비트에서 상위 6비트는 1단계에서 하위 6비트는 2단계에서 사용된다.