#datastructure #database > [!abstract] introduction > 데이터베이스에 있는 데이터를 사용하기 위해서는 수많은 입출력 연산을 거쳐야 합니다. 데이터베이스 수준 정도 되면 캐시나 메모리에 통째로 담기에는 용량이 너무 커서 입출력에 필요한 시간이 연산 시간을 결정하는 가장 큰 요인이 됩니다. 데이터베이스에 대한 연산 속도를 높이기 위해서는 입출력 시간을 줄일 방법이 필요하고, 이를 위해서는 데이터베이스 연산에 특화된 자료구조로 데이터베이스를 저장해야 합니다. 이번 글에서는 데이터베이스 인덱싱에 활용되는 대표적인 자료구조인 B+-Tree를 알아봅니다. # Index 데이터베이스에서 이루어지는 모든 작업은 접근*Access* 기반이다. 데이터베이스 안에서 특정 조건을 만족하는 데이터를 찾는 작업이 Select, Join 등 모든 연산의 출발점이다. 당연히 모든 데이터를 다 훑어보면서 탐색하는 것은 너무 비효율적이니 데이터를 쉽게 알아볼 수 있게 인덱스*Index*를 사용한다. 인덱스의 구체적인 구현에는 연산 유형, 연산 시간, 데이터 삽입 및 삭제에 소요되는 시간, 인덱스가 추가로 차지하는 메모리 공간 등 여러가지 상황이 고려되어야 한다. ## Record 데이터베이스는 물리적으로 파일 시스템 위에 구현되고, 데이터들은 파일의 형태로 저장되어 있는 것이 일반적이다. 파일 안에 저장되어 있는 데이터는 특히 레코드*Record*라 부른다. 효율적인 저장을 위해 레코드들은 연결 리스트*Linked List*의 형태로 저장되어 있으며, 각 레코드는 개체의 모든 속성과 값을 가지고 있다. ## Search Key 인덱스를 구현할 때 공간을 절약하기 위해, 또 데이터베이스의 특성을 활용하기 위해 레코드에 있는 일부 속성 혹은 속성들을 인덱스로 활용하게 되는데 이 속성(들)을 검색 키*Search Key*라 부른다[^1]. 검색 키는 데이터베이스에 저장된 각 레코드마다 하나씩 있으며[^2], 검색 과정에서 레코드를 대표하는 중요한 개념이다. 검색 키와 연결된 인덱스 시스템으로 레코드에 빠르게 접근할 수 있는데, 이때 인덱스를 통해 본 데이터베이스가 물리적으로 저장된 형태와 꼭 동일할 필요는 없다. 검색 키의 값의 순서대로 인덱스를 지정할 수도 있고(Ordered Index), 특정한 함수에 따라 임의로 검색 키를 섞을 수도 있다(Hash Index). 이번 글의 주제인 B+-Tree는 검색 키의 순서를 그대로 사용하는 순서 인덱스*Ordered Index*를 사용한다. 반대로 레코드가 인덱스 체계에 맞게 저장되어 있을 수도 있고, 아닐 수도 있다. 전자의 경우 인덱스의 순서가 레코드가 저장된 순서를 결정하기 때문에 클러스터링 인덱스*Clustering Index* 혹은 주요 인덱스*Primary Index*라 부르며, 후자의 경우 인덱스의 순서가 레코드가 저장된 순서와 다르기 때문에 비클러스터링 인덱스*Nonclustering Index* 혹은 보조 인덱스*Secondary Index*라 부른다. ## Dense & Sparse 인덱스는 보통 테이블의 평태로 관리되는데, 이를 인덱스 엔트리*Index Entry* 혹은 인덱스 레코드*Index Record*라 부른다. 인덱스 엔트리는 검색 키의 값과 그 값을 가지고 있는 레코드를 향하는 포인터로 구성되어 있으며, 그 포인터는 레코드가 저장된 디스크 블록*block*과 레코드를 인식하기 위한 오프셋*offset*으로 구성되어 있다. 순서 인덱스에는 밀접 인덱스*Dense Index*와 희소 인덱스*Sparse Index*가 있는데, 밀접 인덱스는 아래와 같이 인덱스 엔트리에 모든 검색 키의 값이 저장되어 있고, 포인터는 해당 값을 가지는 첫번째 레코드를 향한다. 만약 동일한 속성 값을 가진 레코드가 있다면 그런 레코드는 첫번째 레코드 뒤에 순차적으로 저장된다. ![[DenseIndex.png]]![[SparseIndex.png]] 반면 희소 인덱스는 인덱스 엔트리에 모든 검색 키의 값을 저장하지 않고 일부만 저장한다. 그래서 레코드를 찾을 때는 테이블 상에 존재하는 검색 키 값과 비교한 뒤 그 값보다 작거나 같은 값이 있는 곳부터 순차적으로 레코드를 검색하며, 레코드들이 검색 키의 순서대로 정렬되어 있을 때에만 사용할 수 있다. ### Insertion & Deletion 밀접 인덱스와 희소 인덱스의 차이는 레코드를 추가하고 삭제할 때도 명확하게 드러난다. 밀접 인덱스에서는 레코드를 추가할 때, 1. 인덱스에 검색 키 값이 없으면 시스템은 적절한 위치에 검색 키 값을 인덱스 엔트리에 추가한다. 2. 만약 인덱스 엔트리가 같은 검색 키 값을 가지는 모든 레코드를 가리키고 있다면, 인덱스 엔트리에 새 레코드를 가리키는 포인터를 추가한다. 3. 그렇지 않다면, 인덱스 엔트리는 같은 검색 키 값을 가지는 모든 레코드 중 맨 위에 있는 레코드에 대한 포인터만 가지고 있다. 따라서 같은 검색 키 값을 가지고 있는 다른 모든 레코드 뒤에 새 레코드를 추가한다. 희소 인덱스의 경우, 1. 인덱스가 각 블록에 대한 엔트리를 저장한다는 가정 하에 시스템이 새로운 블록을 생성하면 그 블록에 나타나는 첫번째 검색 값을 인덱스에 넣는다. 2. 반면, 새 레코드가 가장 뒤쪽에 있는 검색 키 값을 가지고 있다면 인덱스 엔트리를 업데이트한다. 3. 그 외에는 시스템이 인덱스를 건드리지 않는다. 레코드를 제거할 때, 밀접 인덱스에서는... 1. 알맞는 검색 키 값을 가진 레코드가 하나만 있다면 인덱스 엔트리에서 그 인덱스를 함께 제거한다. 2. 그렇지 않다면 해당 인덱스 엔트리에서 그 레코드를 가리키는 포인터를 제거한다. 3. 만약 같은 검색 키 값을 가지는 모든 레코드 중 맨 위에 있는 레코드에 대한 포인터를 지워야 한다면 그 다음 레코드를 가리키도록 포인터를 조작한다. 희소 인덱스에서는... 1. 해당 검색 키 값을 포함하는 인덱스 엔트리가 없다면 아무것도 하지 않는다. 2. 만약 해당 검색 키를 가진 유일한 레코드가 삭제됐다면 시스템은 다음 검색 키 값을 가진 레코드로 대체한다. 만약 이미 인덱스 엔트리를 가지고 있다면 엔트리는 삭제된다. 3. 그렇지 않고 해당 검색 키를 가진 레코드가 또 있다면 인덱스 엔트리는 같은 검색 키 값을 가진 다음 레코드를 가리키도록 변경된다. ## Multilevel Indices 앞서 살펴본 인덱싱 기법을 실제 데이터베이스에 적용하려면 한 단계로는 부족하다. 인덱싱을 한번 해도 그 자체가 데이터베이스 수준의 크기를 자랑할 수도 있다. 이럴 때는 아래와 같이 다계층 인덱스*Multilevel Index*를 구현하여 구조를 약간 복잡하게 만드는 대신 공간 복잡도와 평균적인 시간 복잡도를 개선한다. ![[MultilevelSparseIndex.png]] # BST to $B^+$ Tree ## Binary Search Tree 아까 살펴봤던 다계층 구조, 어딘가 낯이 익다. 그렇다. 다계층 인덱스는 근본적으로 트리의 형태를 띠고 있다. 데이터베이스의 물리적 구현에는 트리가 빠질 수 없다. 데이터베이스와 트리의 결합은 다계층 인덱스를 구현하는 과정에서 등장했으며, 가장 기초적인 트리는 이진 탐색 트리*Binary Search Tree*라 볼 수도 있을 것이다. ![[BST.png]] 하지만 데이터베이스에 적용하기에 이진 탐색 트리는 너무 크고, 데이터베이스의 연산 과정에 최적화된 형태도 아니다. 그렇다면 아래처럼 하나의 노드에 여러 값을 넣고 자식 노드도 두개 이상 가질 수 있게 인덱스 트리를 구성할 수도 있겠다. 이러한 방식은 새로 가져오는 데이터는 적은 대신 비교 연산의 비중이 올라가고, 이진 탐색 트리에 가까울수록 비교 연산의 비중은 줄어드는 대신 입출력 연산의 비중은 올라간다. ![[B+Tree-insert.png]] 입출력 연산과 비교 연산 중에 어느 쪽을 줄여야 데이터베이스의 연산 속도가 더 빨라질지는 안봐도 비디오다. ## B-Tree 비교 연산 기반의 트리를 이용한 인덱싱은 B-Tree를 거쳐 $B^+$ 트리로 발전했다. 이진 탐색 트리에서 하나의 노드 당 최대 2개로 제한되었던 자식 노드의 수를 n개로 확장하면 B-Tree가 된다. 그러면서 노드에 값 하나를 두고 탐색 중인 값 하나와 비교했던 것과 달리 이제는 자식 노드가 n개가 되어 비교 결과가 2가지에서 n가지로 늘어났고, 이에 따라 각 구간을 만족하는 자식 노드를 가리키는 포인터 $P_i$와 자신의 검색 키 값인 $K_i$, 그리고 $K_i$가 있는 레코드를 가리키는 포인터 $B_i$ 로 구성되어 있다. ![[B-TreeNode.png]] $K_1, K_2, ..., K_{m-1}$은 트리의 노드에 있는 키 값으로, 자식 노드의 수를 늘리면서 비교 연산의 결과가 단지 노드안에 저장된 하나의 값과의 비교 결과(크거나 작음)가 아닌 $m$개의 구간 중 하나가 되었다. 만약 검색하려는 값과 키 값 중 하나인 $K_i$가 일치한다면, 검색은 종료되고 우리는 검색의 결과인 해당 레코드로 향하는 $B_i$ 포인터를 얻게 된다. 가장 맨 끝 층에 위치한 노드에는 $P_i$가 자식 노드가 아닌 레코드 자체를 가리키기 때문에 $B_i$가 들어가지 않는다. ![[B-Tree.png]] 우리가 검색하려는 값이 어떤 구간에 속하느냐에 따라 도착하게 되는 자식 노드가 달라진다. ## $B^+$-Tree 여기서 한발 더 나아간 것이 바로 $B^+$-Tree이며, 노드의 구조부터 삽입 및 삭제 과정까지 데이터베이스에 최적화된 형태를 가지고 있다. ![[B+Tree.png]] $B^+$-Tree의 노드의 전형적인 구조는 아래와 같다. $B^+$-Tree와 B-Tree의 가장 큰 차이는 레코드르 가리키는 포인터를 저장하는 위치다. B-Tree는 비교 결과 일치하면 바로 레코드에 접근할 수 있는데, $B^+$-Tree는 모든 데이터, 즉 레코드로 향하는 포인터들을 전부 다 리프 노드에 저장한다. ![[B+TreeNode.png]] 리프 노드이건 아니건 노드의 구조는 동일하다. 리프 노드와 그렇지 않은 노드의 차이는 이 구조를 어떻게 활용하냐에 달려 있다. $P_1, P_2, ..., P_n$은 포인터, $K_1, K_2, ..., K_n$은 검색 키 값이며, 노드 안에 있는 포인터의 개수는 그 노드의 팬아웃*fanout*이라 부린다. ![[LeafNodeForB+TreeIndex.png]] 각 리프 노드는 레코드를 직접적으로 가리키는 포인터를 가진다. $P_1, P_2, ..., P_{n-1}$은 각각 검색 키 값이 $K_1, K_2, ..., K_{n-1}$인 레코드를 가리키는 포인터다.[^3] 그리고 마지막 포인터 $P_n$는 다음 리프 노드를 가리킨다. 특이하게도 리프 노드에 저장할 수 있는 값의 개수에는 최소와 최대가 존재하는데, 최소 $\lceil (n-1)/2 \rceil$ 최대 $n-1$개의 값을 가질 수 있다. 또한 두 리프 노드 $L_i$와 $L_j$에 대하여 $i \lt j$일 때, 다시 말해 $L_i$가 $L_j$보다 왼쪽에 있을 때, $L_i$에 있는 모든 검색 키 값 $v_i$는 $L_j$에 있는 모든 검색 키 값보다 커야 한다. 리프 노드가 아닌 나머지 노드는 내부 노드*Internal Node*라고도 부르며, 자식 노드를 가리키는 데 사용한다. 리프 노드와 동일한 구조를 가지고 있지만, 포인터 $P_i$가 레코드가 아닌 자식 노드를 가리키고 마지막 포인터 $P_n$은 다음 자식 노드를 가리킬 때 사용한다. 이들은 리프 노드를 가리키는 다층*multilevel* 인덱스 구조를 가지고 있으며 키 값 $K_1, K_2, ..., K_{n-1}$은 항상 정렬되어 있는데 $i \lt j$이면 $K_i \lt K_j$다. 여기에도 저장할 수 있는 포인터의 최소 개수와 최대 개수가 있는데, 각각 2개와 $\lceil n/2 \rceil$이다.[^4] # $B^+$-Tree의 연산 이제 B+ 트리에서 어떻게 연산이 이루어지는지를 보며 B+ 트리의 구조를 더욱 자세히 살펴보자. ## Query $B^+$-Tree에서 특정 검색 키 값 $v$를 가진 레코드를 찾는 과정은 직관적이다. 루트 노드에서 시작하여 리프 노드에 도달할 때까지 트리를 순회한다. ![[B+TreeQueryPseudoCode.png]] 구체적으로, 현재 노드를 루트로 설정한 뒤 리프 노드에 도달할 때까지 다음 과정을 반복한다. 먼저 현재 노드를 살펴보면서 검색 키 값 $v$보다 크거나 같은 키 값 중 가장 작은 것 $K_i$를 찾는다. 만약 $K_i = v$라면 포인터 $P_{i+1}$이 가리키는 노드로 이동하고, $K_i \gt v$라면 포인터 $P_i$가 가리키는 노드로 이동한다. 그런 키 값을 찾지 못했다면 $v$가 노드의 모든 키 값보다 크다는 뜻이므로 마지막 포인터 $P_m$이 가리키는 노드로 이동한다. 리프 노드에 도달하면 그 안에서 $K_i = v$인 키가 있는지 확인한다. 있다면 해당 포인터 $P_i$가 우리가 찾던 레코드를 가리키므로 이를 반환하고, 없다면 검색 키 값 $v$를 가진 레코드가 존재하지 않는다는 뜻이므로 null을 반환한다. $B^+$-Tree는 단일 값 검색뿐만 아니라 범위 검색*Range Query*도 효율적으로 지원한다. 예를 들어 instructor 테이블에서 급여가 50,000에서 100,000 사이인 모든 강사를 찾는 쿼리를 생각해보자. 범위 검색을 위한 `findRange(lb, ub)` 함수는 다음과 같이 동작한다. ![[B+TreeRangeQueryPseudoCode.png]] 먼저 `find(lb)`와 유사한 방식으로 하한값 $lb$가 있을 리프 노드까지 순회한다. 그 리프 노드에서 $lb$ 이상인 첫 번째 키부터 시작하여, 키 값이 상한값 $ub$를 초과하거나 트리의 끝에 도달할 때까지 순차적으로 리프 노드들을 따라가며 조건을 만족하는 모든 레코드 포인터를 수집한다. 리프 노드들이 연결 리스트로 연결되어 있기 때문에 이러한 순차 탐색이 효율적이다. $B^+$-Tree의 쿼리 성능은 매우 우수하다. $N$개의 레코드가 있을 때 루트에서 리프까지의 경로 길이는 최대 $\lceil \log_{\lceil n/2 \rceil}(N) \rceil$이다. 노드 크기를 디스크 블록 크기와 같게 설정하면(일반적으로 4KB) 검색 키 크기가 12바이트, 포인터 크기가 8바이트일 때 $n$은 약 200 정도가 된다. $n = 100$으로 보수적으로 잡아도 백만 개의 레코드에 대해 단 4번의 노드 접근만으로 검색이 가능하다. 게다가 루트 노드는 자주 접근되므로 대부분 버퍼에 있을 가능성이 높아, 실제로는 보통 3번 이하의 디스크 읽기만으로 검색이 완료된다. ## Insertion $B^+$-Tree에 새로운 레코드를 삽입하는 과정은 기본적으로는 간단하지만, 노드가 가득 찬 경우 노드 분할*node split*이 필요하다는 점에서 복잡성이 생긴다. ![[B+Tree.png]] 먼저 간단한 경우를 보자. 이미 있는 B+ 트리에 "Adams"라는 이름을 가진 instructor 레코드를 삽입한다고 가정하자. 검색 알고리즘을 사용하여 "Adams"가 들어가야 할 리프 노드를 찾는다. 이 경우 "Brandt", "Califieri", "Crick"이 있는 리프 노드가 해당된다. ![[B+TreeInsertAdams.png]] 그런데 이 노드에는 이미 3개의 값이 있어서 공간이 없다($n=4$이므로 리프 노드는 최대 3개의 값만 가질 수 있다). 따라서 노드를 두 개로 분할해야 한다. 4개의 값("Adams", "Brandt", "Califieri", "Crick")을 두 노드로 나눌 때, 처음 $\lceil n/2 \rceil = 2$개는 기존 노드에 두고 나머지는 새 노드에 넣는다. 결과적으로 "Adams"와 "Brandt"는 한 노드에, "Califieri"와 "Crick"은 새 노드에 위치하게 된다. 리프 노드를 분할한 후에는 새 노드를 트리 구조에 추가해야 한다. 새 노드의 최솟값인 "Califieri"와 새 노드를 가리키는 포인터를 부모 노드에 삽입한다. 이 경우 부모 노드에 공간이 있어서 추가 분할 없이 삽입이 완료된다. 이제 더 복잡한 경우를 보자. 앞의 트리에 "Lamport"를 삽입한다고 하자. ![[B+TreeInsertLamport.png]] "Lamport"가 들어가야 할 리프 노드("Gold", "Katz", "Kim")도 이미 가득 차 있어 분할이 필요하다. 4개의 값을 나누면 "Kim"과 "Lamport"가 새 노드로 가게 된다. 그런데 이번에는 부모 노드에 (Kim, $n_1$) 엔트리를 추가하려 할 때 부모 노드도 가득 차 있어서 부모 노드까지 분할해야 한다. 내부 노드의 분할은 리프 노드와 조금 다르다. 부모 노드를 개념적으로 확장하여 새 엔트리를 추가한 뒤, 자식 포인터들을 나눈다. 원래 노드에는 처음 3개의 포인터를 남기고, 새로 생성된 노드에는 나머지 2개의 포인터를 넣는다. 포인터 사이의 키 값들은 이동하는 포인터를 따라가지만, 두 그룹의 포인터 사이에 있던 키 값("Gold")은 특별하게 처리된다. 이 값은 분할된 두 노드 중 어디에도 들어가지 않고, 대신 한 단계 위인 부모 노드로 올라간다. 이 경우 부모가 루트였고 공간이 있어서 "Gold"가 루트에 추가된다. 최악의 경우 분할이 루트까지 전파되어 루트도 분할되어야 할 수 있다. 이 경우 새로운 루트가 생성되고 트리의 높이가 1 증가한다. ![[B+TreeInsertionPseudoCoded.png]] ![[B+TreeSubsidiaryProceduresPseudoCode.png]] 삽입 알고리즘은 재귀적으로 작동한다. 리프 노드에 엔트리를 삽입한 후, 필요하다면 노드를 분할하고 부모 노드에 새로운 엔트리를 삽입한다. 이 과정이 분할이 필요 없는 노드를 만나거나 새로운 루트가 생성될 때까지 반복된다. ## Deletion $B^+$-Tree에서 레코드를 삭제하는 과정은 삽입보다 더 복잡하다. 삭제 후 노드의 엔트리 개수가 최솟값 미만으로 떨어지면 노드 병합*coalescing*이나 재분배*redistribution*가 필요하기 때문이다. 먼저 Figure 14.14의 트리에서 "Srinivasan"을 삭제한다고 가정하자. ![[B+TreeInsertAdams.png]] 검색 알고리즘을 사용하여 "Srinivasan"이 있는 리프 노드를 찾고 해당 엔트리를 삭제한다. 삭제 후 이 노드에는 "Wu" 하나만 남게 되는데, $n=4$일 때 리프 노드는 최소 $\lceil (n-1)/2 \rceil = 2$개의 엔트리를 가져야 하므로 노드가 **과소 상태*underflow***가 된다. ![[B+TreeDeleteSrinivasan.png]] 과소 상태의 노드를 처리하는 방법은 두 가지다. 형제 노드와 병합하거나, 형제 노드에서 엔트리를 빌려오는 것이다. 이 경우 왼쪽 형제 노드("Mozart", "Singh")와 병합할 수 있다. 두 노드의 모든 엔트리를 왼쪽 형제로 옮기고 우측 노드를 삭제한다. 그 다음 부모 노드에서 삭제된 노드를 가리키던 엔트리("Srinivasan", $n_3$)를 제거한다. 부모 노드에서 엔트리를 제거한 후, 이 노드도 과소 상태가 된다(포인터가 하나만 남음). 이번에는 형제 노드("Califieri", "Einstein", "Gold")를 확인해본다. 두 노드를 병합하려면 총 5개의 포인터가 필요한데 최대 4개까지만 가능하므로 병합이 불가능하다. 이런 경우 **재분배**를 수행한다. 왼쪽 형제의 가장 오른쪽 포인터(Gold를 가리키는 포인터)를 과소 상태 노드로 이동시킨다. 하지만 단순히 포인터만 옮기면 안 된다. 원래 부모 노드에 있던 "Mozart"가 이 노드로 내려오고, 대신 "Gold"가 부모 노드로 올라간다. 이렇게 해야 검색 키 값들이 올바른 순서를 유지한다. 이제 "Singh"와 "Wu"를 차례로 삭제해보자. ![[B+TreeDeletionSinghWu.png]] "Singh"의 삭제는 노드를 과소 상태로 만들지 않는다. 하지만 "Wu"를 삭제하면 다시 노드가 과소 상태가 된다. 이번에는 형제 노드와 병합이 불가능하므로 재분배를 수행한다. "Kim"을 과소 상태 노드로 이동시키고, 부모 노드의 구분 값을 "Mozart"에서 "Kim"으로 변경한다. 마지막으로 "Gold"를 삭제하면 더욱 복잡한 상황이 발생한다. "Gold" 삭제 후 리프 노드가 과소 상태가 되고, 이번에는 형제와 병합이 가능하다. 병합 후 부모 노드("Kim"만 있는 내부 노드)에서 엔트리를 삭제하면 이 노드도 과소 상태가 된다. 부모 노드도 형제와 병합할 수 있다. 병합 시 중간에 있던 키 값 "Gold"가 병합된 노드로 내려온다. 이 병합으로 인해 그 부모 노드(루트)에서 엔트리가 삭제되는데, 루트가 자식 포인터 하나만 남게 된다. 루트는 최소 2개의 자식을 가져야 하므로, 이 경우 **루트가 삭제되고 그 유일한 자식이 새로운 루트**가 된다. 이렇게 트리의 높이가 1 감소한다. 흥미로운 점은 삭제의 결과로 어떤 키 값(여기서는 "Gold")이 리프 레벨에서는 사라졌지만 내부 노드에는 여전히 남아있을 수 있다는 것이다. 이는 $B^+$-Tree의 정상적인 상태이며 문제가 되지 않는다. ![[B+TreeDeletionPseudoCode.png]] 삭제 알고리즘도 재귀적으로 작동한다. 리프에서 엔트리를 삭제한 후, 노드가 과소 상태가 되면 병합이나 재분배를 수행하고, 필요시 부모 노드에서도 엔트리를 삭제한다. 이 과정이 노드가 적절한 크기를 유지하게 되거나 루트에 도달할 때까지 반복된다. $B^+$-Tree의 삽입과 삭제 연산의 최악의 경우 복잡도는 모두 $O(\log_{\lceil n/2 \rceil}(N))$이다. 즉, 트리의 높이에 비례한다. 실제로는 대부분의 삽입과 삭제가 리프 레벨에서만 수정이 일어나고 상위 레벨로 전파되지 않아서 평균적으로 매우 빠르다. 팬아웃이 100이라고 가정하면, 삽입 시 노드 분할이 발생할 확률은 1/100에서 1/50 정도에 불과하다. 따라서 평균적으로 삽입은 약간 1개 이상의 I/O 연산만 필요로 한다. --- # 출처 - Silberschatz, A., Korth, H.F. and Sudarshan, S. (2020) _Database system concepts_. Seventh edition. New York, NY: McGraw-Hill. [^1]: 검색 키가 두개 이상의 속성을 참조할 때는 복합 검색 키*Composite Search Key*라 부른다. [^2]: 검색 키가 레코드마다 고유하지 않은 경우도 있는데, 이런 검색 키는 비고유 검색 키*Nonunique Search Key*라 부른다. [^3]: 물론 B+ 트리는 대부분 밀접 인덱스로 사용되기는 하지만, 이는 B+ 트리가 밀접 인덱스로 사용되었을 때의 이야기다. [^4]: 트리가 노드 하나만 있는 게 아니라면 최소 포인터 개수는 무조건 2개다.