프랙탈 트리 지수

프랙탈 트리 지수
프랙탈 트리 지수
유형	나무
발명된	2007
발명된 사람	마이클 A. 벤더, 마틴 패러치-콜튼, 브래들리 C쿠즈마울
큰 O 표기법에서의 시간 복잡성
알고리즘.
알고리즘.
공간
검색
삽입하다
삭제

컴퓨터 과학에서 프랙탈 트리 인덱스는 데이터를 정렬하고 B 트리와 동시에 검색과 순차 액세스가 가능한 트리 데이터 구조로 B 트리보다 점증적으로 빠른 삽입과 삭제를 가지고 있다.B-트리처럼 프랙탈 트리 지수는 한 노드가 두 개 이상의 자식을 가질 수 있다는 점에서 바이너리 검색 트리를 일반화한 것이다.나아가 B-트리와는 달리 프랙탈 트리 인덱스는 각 노드에 버퍼가 있어 삽입, 삭제, 기타 변경 사항을 중간 위치에 저장할 수 있다.버퍼의 목표는 디스크 쓰기를 스케줄링하여 각 쓰기 작업이 많은 양의 유용한 작업을 수행하도록 함으로써 각 디스크 쓰기가 디스크의 소량의 데이터를 변경할 수 있는 최악의 B-tree 성능을 방지하는 것이다.B-트리처럼 프랙탈 트리 인덱스는 대용량 데이터 블록을 읽고 쓰는 시스템에 최적화돼 있다.프랙탈 트리 지수는 토쿠텍에 의해 데이터베이스에서 상용화되었다.원래는 캐시 옵저버 룩어헤드 어레이로 구현되었지만,^[1] 현재 구현은 B 트리의^ε 확장이다.^[2]B는^ε 버퍼링된 리포지토리 트리와 관련이 있다.^[3]완충된 리포지토리 트리는 2도가 있고, B^ε 트리는 B도가^ε 있다.프랙탈 트리 지수는 또한 파일 시스템 프로토타입에 사용되었다.^[4]^[5]프랙탈 트리 지수의 오픈 소스 구현을 이용할 수 있으며,^[6] 이는 아래에 요약된 구현 세부사항을 보여준다.

개요

프랙탈 트리 인덱스에서 내부(잎이 아닌) 노드는 사전 정의된 일부 범위 내에서 하위 노드 수를 가변적으로 가질 수 있다.노드에서 데이터를 삽입하거나 제거하면 하위 노드 수가 변경된다.사전 정의된 범위를 유지하기 위해 내부 노드를 결합하거나 분할할 수 있다.B 트리의 각 내부 노드에는 분기 계수보다 1개 적은 수의 키가 포함될 것이다.키는 하위 트리를 나누는 분리 값 역할을 한다.하위 트리의 키는 검색 트리 순서에 저장된다. 즉, 하위 트리의 모든 키는 두 브래킷 값 사이에 있다.그런 점에서 그들은 꼭 B-tree와 같다.

프랙탈 트리 인덱스와 B 트리는 모두 저장소에서 노드를 가져올 때 크기가 B ${\displaystyle B$ 로 표시되는 메모리 블록이 가져오는 사실을 이용한다.따라서 노드 크기는 대략 B $B$ 로 조정된다 $B$ 스토리지에 대한 액세스가 데이터 구조의 실행 시간을 좌우할 수 있기 때문에 외부 메모리 알고리즘의 시간 복잡성은 데이터 구조가 유도하는 읽기/쓰기 횟수에 의해 좌우된다.(예:^[7] 다음 분석을 참조하십시오.)

B-트리에서는 노드의 키 수가 노드를 채울 수 있을 정도로 충분히 타겟팅되고 노드 분할 및 병합에 대한 약간의 가변성이 있다는 것을 의미한다. $O(B)$ 분석을 위해 O $O(B)$ ( B $O(B)$ ) $O(B)$ 키가 $O(B)$ 노드에 맞으면 트리에 깊이 O $O(\log _{B}N)$ $O(\log _{B}N)$ ⁡ $O(\log _{B}N)$ ) ${\displaystyle O(\log _{B}N)$ 가 있으며 $O(\log _{B}N)$ 이는 검색과 삽입의 I/O 복잡성이다.

Fractal trees nodes use a smaller branching factor, say, of ${\sqrt {B}}$ . The depth of the tree is then $O(\log _{\sqrt {B}}N)=O(\log _{B}N)$ , thereby matching the B-tree asymptotically.각 노드의 나머지 공간은 삽입, 삭제 및 업데이트를 버퍼링하는 데 사용되며, 이를 총체적으로 메시지라고 부른다.완충기가 가득 차면 아이들에게 대량으로 빨개진다.버퍼를 플러시하는 방법에는 여러 가지 선택이 있으며, 모든 것이 유사한 I/O 복잡성으로 이어진다.노드 버퍼의 각 메시지는 키에 의해 결정되는 대로 특정 하위 항목으로 플러시된다.구체성의 경우, 메시지가 동일한 아이로 향하는 것으로 ${\sqrt {B}}+1$ B + ${\sqrt {B}}+1$ {\ $displaystyle$ {\ $sqrt{B}+1$ } 자녀 ${\sqrt {B}}+1$ 중에서 메시지가 가장 많은 것을 선택한다고 가정해 보십시오.그런 다음 ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ 에게 플러시할 수 있는 ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ B ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ + ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ ${\frac {B}{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ ${\$ 의 ${\frac B{{\sqrt {B}}+1}}\approx {\sqrt {B}}$ 메시지가 있다.각 플러시는 $O(1)$ ( $O(1)$ ) ${\displaystyle$ O $(1)}$ 플러시를 $O(1)$ 필요로 하므로 플러시의 메시지당 비용은 $O\left({\frac {1}{\sqrt {B}}}\right)$ ( $O\left({\frac {1}{\sqrt {B}}}\right)$ $O\left({\frac {1}{\sqrt {B}}}\right)$ ) ${\$ 입니다 $O\left({\frac {1}{\sqrt {B}}}\right)$

삽입 비용을 고려하십시오.각 메시지는 $O(\log _{B}N)$ $O(\log _{B}N)$ $O(\log _{B}N)$ $O(\log _{B}N)$ ) $O(\log _{B}N)$ 번 $O(\log _{B}N)$ 플러시되며 플러시 비용은 $O\left({\frac {1}{\sqrt {B}}}\right)$ ) ${\$ 이다 $O\left({\frac {1}{\sqrt {B}}}\right)$ Therefore, the cost of an insertion is $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ . Finally, note that the branching factor can vary, but for any branching factor $B^{\varepsilon }$ , the cost of a flush is ${\displaystyle O\left$ $({\frac {1}{B^{1-\varepsilon }}}\right$ 따라서 검색 트리의 깊이에 따라 달라지는 검색 비용과 그에 따라 가지 계수(branching factor) 간의 원활한 트레이드오프를 제공할 수 있으며, 이는 트리의 깊이에 따라 다르지만 버퍼 플러시의 크기에 더 민감하게 작용한다.

다른 외부 메모리 인덱스와의 비교

이 절에서는 프랙탈 트리 색인을 다른 외부 메모리 인덱싱 데이터 구조와 비교한다.이 주제에 대한 이론 문헌은 매우 크기 때문에, 이 논의는 데이터베이스와 파일 시스템에서 사용되고 있는 인기 있는 데이터 구조와의 비교로 제한된다.

B-tree

B 트리의 검색 시간은 점증상 프랙탈 트리 색인과 동일하다.그러나 프랙탈 트리 지수는 B 트리보다 깊은 트리를 가지고 있으며, 각 노드가 I/O를 요구하려면 캐시가 차가운 경우 프랙탈 트리 인덱스는 더 많은 IO를 유도한다.그러나 많은 워크로드의 경우 B-tree와 프랙탈 트리 인덱스의 대부분의 내부 노드 또는 모든 노드가 이미 RAM에 캐시되어 있다.이 경우 탐색비용은 잎을 가져오는 비용이 지배하는데, 이는 두 경우 모두 마찬가지다.따라서 많은 워크로드의 경우 프랙탈 트리 인덱스는 검색 시간 측면에서 B-tree와 일치할 수 있다.

삽입, 삭제 및 업데이트와 관련하여 서로 다른 경우.프랙탈 트리 색인에 삽입하면 $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O(\log _{B}N)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ ) ${\$ O $\left({\frac {\log _{B}N}{\sqrt{B}}\$ displaysty $O(로그$ $){$ B $displaysty$ O( $로그 _$ {B $}N)$ 가 필요한 반면 $,$ B-tree는 $O(\log _{B}N)$ 따라서 프랙탈 트리 지수는 B-tree보다 $){\displaystyle$ O $({\sqrt{B})$ 의 배수로 더 빠르며 $O({\sqrt {B}})$ $B$ {\ $displaystyle B}$ 은(는 $B$ ) 상당히 클 수 있으므로, 이는 실제로 관측되는 최악의 경우 삽입 시간에서 2차 개선의 잠재적 결과를 산출한다.B-tree와 프랙탈 트리 인덱스는 둘 다 최상의 경우 삽입을 더 빠르게 수행할 수 있다.예를 들어 키를 순차적으로 삽입하는 경우, 두 데이터 구조는 삽입당 $O\left({\frac {1}{B}}\right)$ ( $O\left({\frac {1}{B}}\right)$ B ) ${\$ {1 $}{B}\right)}$ I $O\left({\frac {1}{B}}\right)$ /O를 달성한다.따라서 프랙탈 트리 인덱스는 항상 베스트 케이스에 가까운 반면, 프랙탈 트리 인덱스가 B 트리에 대해 달성하는 실제 속도 향상은 워크로드의 세부사항에 따라 달라진다.

로그 구조화된 병합 트리

LSM(Log-Structured Merge-tree)은 기하급수적으로 증가하는 용량의 두 개 이상의 인덱스 구조로 구성된 데이터 구조를 가리킨다.어느 정도 수준의 나무가 그 용량에 도달하면, 그것은 다음 더 큰 레벨로 합쳐진다.LSM의 IO-복잡성은 수준 간 증가율과 각 수준에서 선택한 데이터 구조와 같은 파라미터에 따라 달라지기 때문에 LSM의 복잡성을 분석하기 위해서는 특정 버전을 선택해야 한다.비교를 위해 삽입 성능의 프랙탈 트리 인덱스와 일치하는 LSM 버전을 선택한다.

LSM이 $O(\log _{B}N)$ $O(\log _{B}N)$ $O(\log _{B}N)$ N $O(\log _{B}N)$ ) ${\displaystyle$ O $(\log _{B}N)}$ B-tree를 $O(\log _{B}N)$ 통해 구현된다고 가정해 보십시오. 각 열량은 이전 ${\sqrt {B}}$ 보다 B ${\$ {\ $sqrt{B}}}%$ 더 크다 ${\sqrt {B}}$ .병합 시간은 다음 세 가지 사실에 따라 달라진다.The sorted order of keys in an $N$ -item B-tree can be produced in $O\left({\frac {N}{B}}\right)$ IOs; Two sorted lists of $N$ and $M$ items can be merged into a sorted list in ${\displaystyle O\left({\frac {N+M}{$ $B$ $}\right)}$ IOs $O\left({\frac {N+M}{B}}\right)$ $,$ $그리고$ N {\displaystyle $N}$ 항목의 $N$ 정렬된 목록의 B 트리는 $O\left({\frac {N}{B}}\right)$ $O\left({\frac {N}{B}}\right)$ B $O\left({\frac {N}{B}}\right)$ ) ${\$ IOs에 $O\left({\frac {N}{B}}\right)$ 빌드할 수 있다.트리가 오버플로되면 크기가 $){\displaystyle O({\sqrt{B}}})$ 인 $O(\sqrt{B})$ 트리에 병합되므로 $k$ $k$ 항목을 $k$ 보유하는 수준에서는 $O\left({\frac {k}{\sqrt {B}}}\right)$ B $){\$ O\ $left({\frac {k}{\sqrt{B}}}}}\}\$ rig}\ $오른쪽$ ) IO $)$ 가 병합되어야 한다.한 항목을 레벨당 한 번 병합할 수 있으며, 프랙탈 트리 색인과 일치하는 총 시간은 $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ N $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ $){\$ 이다 $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$

쿼리 시간은 각 레벨에서 간단히 B-트리 쿼리 시간이다.The query time into the $i$ ^th level is $O(\log _{B}B^{\frac {i}{2}})=O(i)$ , since the $i$ ^th level has capacity $B^{\frac {i}{2}}$ .따라서 총 시간은 $O(\log _{B}^{2}N)$ $O(\log _{B}^{2}N)$ $O(\log _{B}^{2}N)$ $O(\log _{B}^{2}N)$ $O(\log _{B}^{2}N)$ ) $O(\log _{B}^{2}N)$ 입니다 $O(\log _{B}^{2}N)$ 이것은 로그 인자에 의한 B-트리 및 프랙탈 트리 지수보다 크다.사실, B-tree와 프랙탈 트리 지수는 삽입과 쿼리 사이의 최적의 트레이드오프 곡선에 있지만, LSM은 그렇지 않다.B트리와 비교할 수 없을 정도로 프랙탈 트리 인덱스가 지배하고 있다.

LSM에 대한 몇 가지 참고 사항: 쿼리를 더 빨리 만드는 방법이 있다.예를 들어 멤버십 쿼리만 필요하며 후속/predercessor/range 쿼리가 없는 경우, BLOOM 필터를 사용하여 쿼리 속도를 높일 수 있다.또한 수준 간의 성장 계수를 다른 값으로 설정할 수 있어 삽입/쿼리 트레이드오프가 다양하다.그러나 삽입률의 모든 선택에서 해당 프랙탈 트리 색인은 더 빠른 쿼리를 가진다.

B나무^ε

프랙탈 트리 지수는 B 트리의^ε 정제다.B^ε 트리처럼 키와 버퍼가 있는 노드로 구성되며 최적의 삽입/쿼리 트레이드오프를 실현한다.프랙탈 트리 지수는 성능 최적화 포함과 기능 확장 면에서 차이가 있다.개선된 기능성의 예로는 AIDS 의미론을 들 수 있다.AIDS 의미론의 B-트리 구현은 일반적으로 활성 트랜잭션에 관련된 행을 잠그는 것을 포함한다.그러한 계획은 삽입과 질의가 모두 같은 잎을 메모리로 가져오는 것을 포함하기 때문에 B-트리에서는 잘 작동한다.따라서 삽입된 행을 잠그면 IO 페널티가 발생하지 않는다.그러나 프랙탈 트리 색인에서 삽입은 메시지로서 행은 동시에 둘 이상의 노드에 존재할 수 있다.따라서 프랙탈 트리 인덱스는 AID 의미론 구현에 수반되는 잠금을 구현하기 위해 IO 효율적이거나 메모리에 상주하는 별도의 잠금 구조를 필요로 한다.

프랙탈 트리 인덱스에도 여러 가지 성능 최적화가 있다.첫째, 버퍼는 검색 속도를 높이기 위해 자체 인덱싱된다.둘째, 잎은 B-tree보다 훨씬 크기 때문에 더 큰 압축을 할 수 있다.실제로 잎은 접근 시간이 대역폭 시간에 의해 지배될 만큼 충분히 큰 것으로 선택되고, 따라서 탐색 및 회전 지연 시간을 상각한다.큰 잎은 큰 범위 쿼리를 가지고 있지만 포인트 쿼리를 느리게 하는 장점이 있는데, 이것은 잎의 작은 부분에 접근해야 한다.프랙탈 트리 인덱스에서 구현되는 솔루션은 빠른 범위 조회를 위해 전체적으로 가져올 수 있지만 개별적으로 가져올 수 있는 콜 지하 노드(call bround node)로 세분되는 큰 잎을 갖는 것이다.대역폭 시간이 단축되었기 때문에 지하 노드에 접근하는 것이 리프에 접근하는 것보다 빠르다.따라서^ε 프랙탈 트리 색인에 있는 잎의 하부 구조는 B 트리와 비교하여 범위와 포인트 질의를 모두 빠르게 할 수 있다.

메시징 및 프랙탈 트리 인덱스

삽입, 삭제, 업데이트는 잎을 향해 나아가는 버퍼에 메시지로 삽입된다.메시징 인프라는 다양한 다른 작업을 구현하기 위해 이용될 수 있으며, 그 중 일부는 아래에서 논의한다.

업서츠

upsert는 행이 존재하지 않을 경우 행을 삽입하고, 없을 경우 행을 업데이트하는 문이다.B-트리에서는 검색 결과에 따라 먼저 행을 검색한 다음 삽입 또는 업데이트를 구현하여 업서트를 구현한다.이렇게 하려면 행이 아직 캐시되지 않은 경우 행을 메모리로 가져와야 한다.프랙탈 트리 지수는 특별한 업퍼트 메시지를 삽입하여 업퍼트를 구현할 수 있다.그러한 메시지는 이론적으로 업데이트 중에 임의의 코드 조각들을 구현할 수 있다.실제로 네 가지 업데이트 작업이 지원된다.

$x:={\text{data}$
$x:=x+{\text{constant}}$ $x:=x+{\text{constant}}$ $x:=x+{\text{constant}}$ + $x:=x+{\text{constant}}$ ${\$ 일반화된 증분)
$x:=x-{\text{constant}}$ $x:=x-{\text{constant}}$ $x:=x-{\text{constant}}$ - $x:=x-{\text{constant}}$ ${\$ 인 감소 $)$
$x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ = $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ 이면 $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ = $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ 이면 0 x $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ - 1 $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\neq 0\end{cases}}$ if 0 $displaystyle$ x $:={\case}0&{\text}{{}x=0\x-1&{\text{}}}}}{}$ 0에 바닥이 있는 경우 $감소)$

이는 페이스북이 제안한 벤치마크인 ^[8]LinkBench에서 사용하는 업데이트 작업에 해당한다.초기 검색을 피함으로써, 업서트 메시지는 규모 순서로 업서트의 속도를 향상시킬 수 있다.

스키마 변경

지금까지 모든 메시지 유형은 단일 행을 수정했다.그러나 모든 발신 버퍼에 복사되는 브로드캐스트 메시지는 데이터베이스의 모든 행을 수정할 수 있다.예를 들어, 브로드캐스트 메시지를 사용하여 데이터베이스의 모든 행 형식을 변경할 수 있다.모든 행을 변경하는 데 필요한 총 작업은 테이블을 가로지르는 브루트 포스 방식에서는 변경되지 않지만, 일단 메시지가 루트 버퍼에 주입되면 이후의 모든 쿼리는 그들이 마주치는 어떤 행에도 스키마 수정을 적용할 수 있기 때문에 대기 시간이 개선된다.스키마 변경은 즉시 이루어지며, 그 작업은 버퍼 오버플로우 및 나뭇잎이 어차피 업데이트되었을 그런 시기로 미루어진다.

구현

프랙탈 트리 지수는 토쿠텍이 구현하고 상용화했다.MySQL과 MariaDB의 스토리지 엔진으로 TokuDB로, MongoDB와의 보다 완벽한 통합이 가능한 TokuMX로 이용 가능하다.프랙탈 트리 인덱스는 프로토타입 파일 시스템인 TokuFS와^[4] BetrFS에서도 사용되었다.^[5]

참조

^ Bender, M. A.; Farach-Colton, M.; Fineman, J.; Fogel, Y.; Kuszmaul, B.; Nelson, J. (June 2007). "Cache-Oblivious streaming B-trees". Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures. CA: ACM Press: 81–92.
^ Brodal, G.; Fagerberg, R. (Jan 2003). "Lower Bounds for External Memory Dictionaries". Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. N.Y.: ACM Press: 546–554.
^ Buchsbaum, A.; Goldwasswer, M.; Venkatasubramanian, S.; Westbrook, J. (Jan 2000). "On External Memory Graph Traversal". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms: 859–860. CiteSeerX 10.1.1.27.9904.
^ ^a ^b Esmet, J.; Bender, M.; Farach-Colton, M.; Kuszmaul, B. (June 2012). "The TokuFS Streaming File System" (PDF). Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems. MA: USENIX Association. pp. 14–14.
^ ^a ^b Jannen, William; Yuan, Jun; Zhan, Yang; Akshintala, Amogh; Esmet, John; Jiao, Yizheng; Mittal, Ankur; Pandey, Prashant; Reddy, Phaneendra; Walsh, Leif; Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Kuszmaul, Bradley C.; Porter, Donald E. (February 2015). "BetrFS: A Right-Optimized Write-Optimized File System" (PDF). Proceedings of the 13th USENIX Conference on File and Storage Technologies. Santa Clara, California.
^ 기투브 리포지토리
^ Cormen, T.; Leiserson, C.E.; Rivest, R.; Stein, C. (2001). "Introduction to Algorithms" (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ Armstrong, T.; Ponnekanti, V.; Borthakur, D.; Callaghan, M. (2013). "LinkBench: A Database Benchmark Based on the Facebook Social Graph". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. NY: ACM Press: 1185–1196.

[cola-1] Bender, M. A.; Farach-Colton, M.; Fineman, J.; Fogel, Y.; Kuszmaul, B.; Nelson, J. (June 2007). "Cache-Oblivious streaming B-trees". Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures. CA: ACM Press: 81–92.

[2] Brodal, G.; Fagerberg, R. (Jan 2003). "Lower Bounds for External Memory Dictionaries". Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. N.Y.: ACM Press: 546–554.

[3] Buchsbaum, A.; Goldwasswer, M.; Venkatasubramanian, S.; Westbrook, J. (Jan 2000). "On External Memory Graph Traversal". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms: 859–860. CiteSeerX 10.1.1.27.9904.

[tokufs-4] Esmet, J.; Bender, M.; Farach-Colton, M.; Kuszmaul, B. (June 2012). "The TokuFS Streaming File System" (PDF). Proceedings of the 4th USENIX Conference on Hot Topics in Storage and File Systems. MA: USENIX Association. pp. 14–14.

[betrfs-5] Jannen, William; Yuan, Jun; Zhan, Yang; Akshintala, Amogh; Esmet, John; Jiao, Yizheng; Mittal, Ankur; Pandey, Prashant; Reddy, Phaneendra; Walsh, Leif; Bender, Michael; Farach-Colton, Martin; Johnson, Rob; Kuszmaul, Bradley C.; Porter, Donald E. (February 2015). "BetrFS: A Right-Optimized Write-Optimized File System" (PDF). Proceedings of the 13th USENIX Conference on File and Storage Technologies. Santa Clara, California.

[ftisource-6] 기투브 리포지토리

[clrs-7] Cormen, T.; Leiserson, C.E.; Rivest, R.; Stein, C. (2001). "Introduction to Algorithms" (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[link_bench-8] Armstrong, T.; Ponnekanti, V.; Borthakur, D.; Callaghan, M. (2013). "LinkBench: A Database Benchmark Based on the Facebook Social Graph". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. NY: ACM Press: 1185–1196.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

v t 잘 알려진 데이터 구조
종류들	컬렉션 컨테이너
추상적	연관 배열 멀티맵 검색 데이터 구조 리스트 쌓다 큐 더블엔드 큐 우선 순위 대기열 이중 종료 우선 순위 대기열 세트 멀티셋 디스조인트
배열	비트 배열 원형완충기 동적 배열 해시 테이블 해시드 배열 트리 희소 행렬
연결됨	연관 리스트 링크 리스트 목록 건너뛰기 연결 해제 목록 XOR 연결 목록
나무들	B-트리 이진 검색 트리 AA 나무 AVL 트리 붉은-검은 나무 자기균형나무 스플레이 트리 힙 이진 힙 이항 힙 피보나치 더미 R-트리 R* 트리 R+ 트리 힐베르트 R 트리 트라이 해시 트리
그래프	이진결정도 방향 아세클릭 그래프 지시된 반복 단어 그래프
데이터 구조 목록

Search

프랙탈 트리 지수

네임스페이스

더

목차

개요