Radix tree1 Radix Tree user level 구현과 커널 소스코드(ver 4.18)와의 비교 - Radix Tree커널 내부 Key-Value 타입의 데이터 구조로, page caching에 이용되는 자료구조이다.리눅스 커널 4.19버전부터 xarray로 대체되고 있다.Tree라기보단 extensible array 구조라고 볼 수 있다.- Radix Tree 기본 구조 각 노드는 64개(또는 48개)의 자식을 가지며, 최상위 노드를 가리키는 Root 구조체가 있다.Internal node의 슬롯은 자식 노드에 대한 포인터, leaf node의 슬롯은 저장된 값(item)에 대한 포인터값을 가진다.각 노드는 (shift,offset)값으로 위치를 알 수 있다. shift는 노드의 높이, offset은 부모 노드의 몇번째 슬롯인지를 알려준다.- Radix Tree 함수- extend(index)처음.. 2021. 1. 12. 이전 1 다음
