전통적인 이진 검색 트리의 한계는 실망스러울 수 있습니다. 대용량 데이터를 손쉽게 처리할 수 있는 다재다능한 데이터 구조, B-Tree를 만나보세요. 대량의 데이터를 저장하고 검색할 때 기존 이진 검색 트리는 성능이 낮고 메모리 사용량이 높아 실용적이지 않을 수 있습니다. B-트리(B-Tree) 또는 균형 트리(Balanced Tree)라고도 알려진 B-트리는 이러한 한계를 극복하기 위해 특별히 설계된 자체 균형 트리 유형입니다.
기존 이진 검색 트리와 달리 B-트리는 단일 노드에 저장할 수 있는 키의 수가 많기 때문에 대형 키 트리라고도 알려져 있습니다. B-트리의 각 노드에는 여러 개의 키가 포함될 수 있으며, 이를 통해 트리는 더 큰 분기 요소를 가지므로 더 낮은 높이를 가질 수 있습니다. 높이가 낮으면 디스크 I/O가 줄어들어 검색 및 삽입 작업이 더 빨라집니다. B-트리는 하드 드라이브, 플래시 메모리, CD-ROM과 같이 느리고 대용량 데이터 액세스가 가능한 스토리지 시스템에 특히 적합합니다.
B-트리는 각 노드에 최소 개수의 키가 있는지 확인하여 균형을 유지하므로 트리는 항상 균형을 유지합니다. 이러한 균형은 트리의 초기 모양에 관계없이 삽입, 삭제, 검색과 같은 작업의 시간 복잡도가 항상 O(log n)임을 보장합니다.
B-트리의 시간 복잡도:
| 아니요. | 연산 | 시간 복잡도 |
|---|---|---|
| 1. | 찾다 | O(로그 n) |
| 2. | 끼워 넣다 | O(로그 n) |
| 삼. | 삭제 | O(로그 n) |
메모: n은 B-트리의 총 요소 수입니다.
자바 카운터
B-트리의 속성:
- 모든 잎은 같은 수준에 있습니다.
- B-Tree는 최소 차수 '라는 용어로 정의됩니다. 티 '. 의 가치 ' 티 '는 디스크 블록 크기에 따라 다릅니다.
- 루트를 제외한 모든 노드에는 최소한 t-1개의 키가 포함되어야 합니다. 루트에는 최소한의 내용이 포함될 수 있습니다. 1 열쇠.
- 모든 노드(루트 포함)에는 최대( 2*티 – 1 ) 키.
- 노드의 자식 수는 해당 노드의 키 수에 더한 값과 같습니다. 1 .
- 노드의 모든 키는 오름차순으로 정렬됩니다. 두 키 사이의 자식 k1 그리고 k2 다음 범위의 모든 키를 포함합니다. k1 그리고 k2 .
- B-트리는 이진 검색 트리와 달리 루트에서 성장하고 축소됩니다. 이진 검색 트리는 아래로 성장하고 아래로 축소됩니다.
- 다른 균형 이진 검색 트리와 마찬가지로 검색, 삽입, 삭제의 시간 복잡도는 O(log n)입니다.
- B-Tree에 노드를 삽입하는 것은 Leaf Node에서만 발생합니다.
다음은 최소 차수가 5인 B-트리의 예입니다.
메모: 실제 B-트리에서는 최소 차수의 값이 5보다 훨씬 큽니다.
위 다이어그램에서 모든 리프 노드는 동일한 레벨에 있고 리프가 아닌 모든 노드에는 빈 하위 트리가 없으며 키가 자식 수보다 1 적은 것을 볼 수 있습니다.
B-나무에 대한 흥미로운 사실:
- n개의 노드로 존재할 수 있는 B-트리의 최소 높이는 다음과 같습니다. m은 노드의 최대 자식 수입니다.
- n개의 노드로 존재할 수 있는 B-트리의 최대 높이는 루트가 아닌 노드가 가질 수 있는 최소 하위 노드 수인 t입니다.
그리고
B-트리에서의 순회:
탐색은 이진 트리의 중위 탐색과도 유사합니다. 가장 왼쪽 자식부터 시작하여 가장 왼쪽 자식을 반복적으로 인쇄한 다음 나머지 자식과 키에 대해 동일한 프로세스를 반복합니다. 마지막으로 가장 오른쪽 자식을 재귀적으로 인쇄합니다.
B-트리에서의 검색 작업:
검색은 이진 검색 트리의 검색과 유사합니다. 검색할 키를 k로 둡니다.
- 루트에서 시작하여 재귀적으로 아래로 탐색합니다.
- 방문한 모든 리프가 아닌 노드에 대해
- 노드에 키가 있으면 간단히 노드를 반환합니다.
- 그렇지 않으면 노드의 적절한 자식(첫 번째 큰 키 바로 앞에 있는 자식)으로 되돌아갑니다.
- 리프 노드에 도달했지만 리프 노드에서 k를 찾지 못하면 NULL을 반환합니다.
B-트리를 검색하는 것은 이진 트리를 검색하는 것과 유사합니다. 알고리즘은 유사하며 재귀를 사용합니다. 각 수준에서 검색은 마치 키 값이 상위 범위에 존재하지 않고 키가 다른 분기에 존재하는 것처럼 최적화됩니다. 이러한 값은 검색을 제한하므로 제한 값 또는 분리 값이라고도 합니다. 리프 노드에 도달했는데 원하는 키를 찾지 못하면 NULL이 표시됩니다.
B-트리에서 요소를 검색하는 알고리즘:-
C++
struct> Node {> >int> n;> >int> key[MAX_KEYS];> >Node* child[MAX_CHILDREN];> >bool> leaf;> };> Node* BtreeSearch(Node* x,>int> k) {> >int> i = 0;> >while> (i n && k>x->키[i]) {> >i++;> >}> >if> (i n && k == x->키[i]) {> >return> x;> >}> >if> (x->잎) {> >return> nullptr;> >}> >return> BtreeSearch(x->자식[i], k);> }> |
>
>
씨
BtreeSearch(x, k)> >i = 1> > >// n[x] means number of keys in x node> >while> i ? n[x] and k ? keyi[x]> >do> i = i + 1> >if> i n[x] and k = keyi[x]> >then>return> (x, i)> >if> leaf [x]> >then>return> NIL> >else> >return> BtreeSearch(ci[x], k)> |
>
>
자바
class> Node {> >int> n;> >int>[] key =>new> int>[MAX_KEYS];> >Node[] child =>new> Node[MAX_CHILDREN];> >boolean> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i =>0>;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
파이썬3
class> Node:> >def> __init__(>self>):> >self>.n>=> 0> >self>.key>=> [>0>]>*> MAX_KEYS> >self>.child>=> [>None>]>*> MAX_CHILDREN> >self>.leaf>=> True> def> BtreeSearch(x, k):> >i>=> 0> >while> i and k>= x.key[i]: i += 1 if i and k == x.key[i]: return x if x.leaf: return None return BtreeSearch(x.child[i], k)> |
>
>
씨#
class> Node {> >public> int> n;> >public> int>[] key =>new> int>[MAX_KEYS];> >public> Node[] child =>new> Node[MAX_CHILDREN];> >public> bool> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
자바스크립트
// Define a Node class with properties n, key, child, and leaf> class Node {> >constructor() {> >this>.n = 0;> >this>.key =>new> Array(MAX_KEYS);> >this>.child =>new> Array(MAX_CHILDREN);> >this>.leaf =>false>;> >}> }> // Define a function BtreeSearch that takes in a Node object x and an integer k> function> BtreeSearch(x, k) {> >let i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }> |
>
>
예:
자바 스레드 생성
입력: 주어진 B-Tree에서 120을 검색합니다.
해결책:
컴퓨터의 종류
이 예에서는 값을 포함하는 키가 존재할 수 있는 가능성을 제한함으로써 검색이 감소했음을 알 수 있습니다. 마찬가지로 위의 예에서 180을 찾아야 한다면 프로그램이 키 180이 현재 노드 내에 존재한다는 것을 발견하기 때문에 제어는 2단계에서 중지됩니다. 마찬가지로 90을 찾는 경우 90 <100이므로 자동으로 왼쪽 하위 트리로 이동하므로 제어 흐름은 위의 예에 표시된 것과 유사하게 진행됩니다.
다음은 위의 접근 방식을 구현한 것입니다.
C++
// C++ implementation of search() and traverse() methods> #include> using> namespace> std;> // A BTree node> class> BTreeNode {> >int>* keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode** C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> public>:> >BTreeNode(>int> _t,>bool> _leaf);>// Constructor> >// A function to traverse all nodes in a subtree rooted> >// with this node> >void> traverse();> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode*> >search(>int> k);>// returns NULL if k is not present.> >// Make the BTree friend of this so that we can access> >// private members of this class in BTree functions> >friend> class> BTree;> };> // A BTree> class> BTree {> >BTreeNode* root;>// Pointer to root node> >int> t;>// Minimum degree> public>:> >// Constructor (Initializes tree as empty)> >BTree(>int> _t)> >{> >root = NULL;> >t = _t;> >}> >// function to traverse the tree> >void> traverse()> >{> >if> (root != NULL)> >root->트래버스();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->검색(k);> >}> };> // Constructor for BTreeNode class> BTreeNode::BTreeNode(>int> _t,>bool> _leaf)> {> >// Copy the given minimum degree and leaf property> >t = _t;> >leaf = _leaf;> >// Allocate memory for maximum number of possible keys> >// and child pointers> >keys =>new> int>[2 * t - 1];> >C =>new> BTreeNode*[2 * t];> >// Initialize the number of keys as 0> >n = 0;> }> // Function to traverse all nodes in a subtree rooted with> // this node> void> BTreeNode::traverse()> {> >// There are n keys and n+1 children, traverse through n> >// keys and first n children> >int> i;> >for> (i = 0; i // If this is not leaf, then before printing key[i], // traverse the subtree rooted with child C[i]. if (leaf == false) C[i]->횡단(); 시합<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->횡단(); } // 이 노드를 루트로 하는 하위 트리에서 키 k를 검색하는 함수 BTreeNode* BTreeNode::search(int k) { // k보다 크거나 같은 첫 번째 키를 찾습니다 int i = 0; while (i 키[i]) i++; // 찾은 키가 k와 같으면 이 노드를 반환합니다. if (keys[i] == k) return this; // 여기에서 키를 찾을 수 없고 이것이 리프 노드인 경우 if (leaf == true) return NULL; // 적절한 자식으로 이동 return C[i]->search(k); }> |
>
>
자바
// Java program to illustrate the sum of two numbers> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >System.out.println();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >boolean> >leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>boolean> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[>2> * t ->1>];> >this>.C =>new> BTreeNode[>2> * t];> >this>.n =>0>;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i =>0>;> >for> (i =>0>; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >System.out.print(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i =>0>;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> |
>
>
파이썬3
# Create a node> class> BTreeNode:> >def> __init__(>self>, leaf>=>False>):> >self>.leaf>=> leaf> >self>.keys>=> []> >self>.child>=> []> # Tree> class> BTree:> >def> __init__(>self>, t):> >self>.root>=> BTreeNode(>True>)> >self>.t>=> t> ># Insert node> >def> insert(>self>, k):> >root>=> self>.root> >if> len>(root.keys)>=>=> (>2> *> self>.t)>-> 1>:> >temp>=> BTreeNode()> >self>.root>=> temp> >temp.child.insert(>0>, root)> >self>.split_child(temp,>0>)> >self>.insert_non_full(temp, k)> >else>:> >self>.insert_non_full(root, k)> ># Insert nonfull> >def> insert_non_full(>self>, x, k):> >i>=> len>(x.keys)>-> 1> >if> x.leaf:> >x.keys.append((>None>,>None>))> >while> i>>=> 0> and> k[>0>] 0]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i>= 0 및 k[0] 0]: i -= 1 i += 1 if len(x.child[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k[0]> x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # 자식 분할 def Split_child(self, x, i): t = self .t y = x.child[i] z = BTreeNode(y.leaf) x.child.insert(i + 1, z) x.keys.insert(i, y.keys[t - 1]) z.keys = y.keys[t: (2 * t) - 1] y.keys = y.keys[0: t - 1] 그렇지 않은 경우 y.leaf: z.child = y.child[t: 2 * t] y. child = y.child[0: t - 1] # 트리를 인쇄합니다 def print_tree(self, x, l=0): print('Level ', l, ' ', len(x.keys), end=':') for i in x.keys: print(i, end=' ') print() l += 1 if len(x.child)> 0: for i in x.child: self.print_tree(i, l) # 트리에서 검색 키 def search_key(self, k, x=None): x가 None이 아닌 경우: i = 0 while i |
>
>
씨#
// C# program to illustrate the sum of two numbers> using> System;> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >Console.WriteLine();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>bool> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[2 * t - 1];> >this>.C =>new> BTreeNode[2 * t];> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i = 0;> >for> (i = 0; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >Console.Write(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >public> BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i = 0;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by Rajput-Ji> |
>
>
자바스크립트
// Javascript program to illustrate the sum of two numbers> // A BTree> class Btree> {> >// Constructor (Initializes tree as empty)> >constructor(t)> >{> >this>.root =>null>;> >this>.t = t;> >}> > >// function to traverse the tree> >traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >document.write(>' '>);> >}> > >// function to search a key in this tree> >search(k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> > }> // A BTree node> class BTreeNode> {> >// Constructor> >constructor(t,leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> Array(2 * t - 1);> >this>.C =>new> Array(2 * t);> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted with this node> >traverse()> >{> >// There are n keys and n+1 children, traverse through n keys> >// and first n children> >let i = 0;> >for> (i = 0; i <>this>.n; i++) {> > >// If this is not leaf, then before printing key[i],> >// traverse the subtree rooted with child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >document.write(keys[i] +>' '>);> >}> > >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> > >// A function to search a key in the subtree rooted with this node.> >search(k)>// returns NULL if k is not present.> >{> > >// Find the first key greater than or equal to k> >let i = 0;> >while> (i keys[i])> >i++;> > >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> > >// If the key is not found here and this is a leaf node> >if> (leaf ==>true>)> >return> null>;> > >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by patel2127> |
>
>
메모: 위 코드에는 드라이버 프로그램이 포함되어 있지 않습니다. 다음 게시물에서는 전체 프로그램을 다룰 예정입니다. B-트리 삽입 .
B-트리를 정의하는 데에는 두 가지 규칙이 있습니다. 하나는 최소 차수로 정의하는 것이고, 두 번째는 순서로 정의하는 것입니다. 우리는 최소 학위 규칙을 따랐으며 B-Tree의 향후 게시물에서도 동일한 내용을 따를 것입니다. 위 프로그램에서 사용된 변수명 역시 동일하게 유지됩니다.
컴퓨터를 정의하다
B-트리의 응용:
- 대규모 데이터베이스에서 디스크에 저장된 데이터에 액세스하는 데 사용됩니다.
- B-Tree를 사용하면 데이터 세트에서 데이터를 훨씬 더 짧은 시간에 검색할 수 있습니다.
- 인덱싱 기능을 사용하면 다단계 인덱싱이 가능합니다.
- 대부분의 서버도 B-트리 접근 방식을 사용합니다.
- B-트리는 CAD 시스템에서 기하학적 데이터를 구성하고 검색하는 데 사용됩니다.
- B-트리는 자연어 처리, 컴퓨터 네트워크, 암호화 등 다른 분야에서도 사용됩니다.
B-트리의 장점:
- B-트리는 삽입, 삭제, 검색과 같은 기본 작업에 대해 O(log n)의 시간 복잡도를 보장하므로 대규모 데이터 세트 및 실시간 애플리케이션에 적합합니다.
- B-트리는 자체 균형을 유지합니다.
- 높은 동시성 및 높은 처리량.
- 효율적인 스토리지 활용.
B-트리의 단점:
- B-트리는 디스크 기반 데이터 구조를 기반으로 하며 디스크 사용량이 높을 수 있습니다.
- 모든 경우에 최선은 아닙니다.
- 다른 데이터 구조에 비해 속도가 느립니다.
삽입 및 삭제:
B-트리 삽입
B-트리 삭제