B-tree

Dalam tutorial ini, Anda akan mempelajari apa itu B-tree. Selain itu, Anda akan menemukan contoh kerja operasi pencarian pada pohon-B di C, C ++, Java dan Python.

B-tree adalah tipe khusus dari pohon pencarian self-balancing di mana setiap node dapat berisi lebih dari satu kunci dan dapat memiliki lebih dari dua anak. Ini adalah bentuk umum dari pohon pencarian biner.

Ia juga dikenal sebagai pohon m-way dengan ketinggian seimbang.

B-tree

Mengapa B-tree?

Kebutuhan B-tree muncul seiring dengan meningkatnya kebutuhan akan waktu yang lebih singkat dalam mengakses media penyimpanan fisik seperti hard disk. Perangkat penyimpanan sekunder lebih lambat dengan kapasitas yang lebih besar. Ada kebutuhan untuk jenis struktur data yang meminimalkan akses disk.

Struktur data lain seperti pohon pencarian biner, pohon avl, pohon merah-hitam, dll hanya dapat menyimpan satu kunci dalam satu node. Jika Anda harus menyimpan kunci dalam jumlah besar, maka ketinggian pohon tersebut menjadi sangat besar dan waktu akses bertambah.

Namun, B-tree dapat menyimpan banyak kunci dalam satu node dan dapat memiliki beberapa node turunan. Ini menurunkan ketinggian secara signifikan sehingga memungkinkan akses disk lebih cepat.

Properti B-tree

  1. Untuk setiap node x, kunci disimpan dalam urutan yang meningkat.
  2. Di setiap node, ada nilai boolean x.leaf yang bernilai true jika x adalah daun.
  3. Jika n adalah urutan pohon, setiap node internal dapat berisi paling banyak n - 1 kunci bersama dengan penunjuk ke setiap anak.
  4. Setiap node kecuali root dapat memiliki paling banyak n turunan dan paling tidak n / 2 turunan.
  5. Semua daun memiliki kedalaman yang sama (yaitu tinggi-h pohon).
  6. Akar memiliki setidaknya 2 anak dan berisi minimal 1 kunci.
  7. Jika n ≧ 1, maka untuk sembarang n-key B-tree dengan tinggi h dan derajat minimum t ≧ 2, .h ≧ logt (n+1)/2

Operasi

Mencari

Mencari elemen dalam B-tree adalah bentuk umum dari pencarian elemen dalam Binary Search Tree. Langkah-langkah berikut diikuti.

  1. Mulai dari simpul akar, bandingkan k dengan kunci pertama dari simpul tersebut.
    Jika k = the first key of the node, kembalikan node dan index.
  2. Jika k.leaf = true, kembalikan NULL (yaitu tidak ditemukan).
  3. Jika k < the first key of the root node, telusuri anak kiri kunci ini secara rekursif.
  4. Jika ada lebih dari satu kunci di simpul saat ini dan k> the first key, bandingkan k dengan kunci berikutnya di simpul.
    Jika k < next key, cari anak kiri dari kunci ini (mis. K terletak di antara kunci pertama dan kedua).
    Lain, cari anak kunci yang tepat.
  5. Ulangi langkah 1 hingga 4 hingga daunnya tercapai.

Contoh Pencarian

  1. Mari kita cari kunci k = 17di pohon di bawah derajat 3. B-tree
  2. k tidak ditemukan di root jadi, bandingkan dengan kunci root. k tidak ditemukan pada simpul akar
  3. Sejak k> 11, pergi ke anak kanan dari simpul akar. Pergi ke subtree kanan
  4. Bandingkan k dengan 16. Karena k> 16, bandingkan k dengan kunci berikutnya 18. Bandingkan dengan kunci dari kiri ke kanan
  5. Karena k < 18, k terletak antara 16 dan 18. Cari di anak kanan 16 atau anak kiri 18. k terletak di antara 16 dan 18
  6. k ditemukan. k ditemukan

Algoritma untuk Mencari Elemen

 BtreeSearch(x, k) i = 1 while i ≦ n(x) and k ≧ keyi(x) // n(x) means number of keys in x node 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)

Untuk mempelajari lebih lanjut tentang operasi B-tree yang berbeda, silakan kunjungi

  • Penyisipan di B-tree
  • Penghapusan pada B-tree

Contoh Python, Java dan C / C ++

Python Java C ++ 
# Searching a key on a B-tree in Python # Create node class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = () self.child = () class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t # Print the tree 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) # Search key def search_key(self, k, x=None): if x is not None: i = 0 while i x.keys(i)(0): i += 1 if i  = 0 and k(0)  = 0 and k(0)  x.keys(i)(0): i += 1 self.insert_non_full(x.child(i), k) # Split def split(self, x, i): t = self.t y = x.child(i) z = BTreeNode(y.leaf) x.child.insert_key(i + 1, z) x.keys.insert_key(i, y.keys(t - 1)) z.keys = y.keys(t: (2 * t) - 1) y.keys = y.keys(0: t - 1) if not y.leaf: z.child = y.child(t: 2 * t) y.child = y.child(0: t - 1) def main(): B = BTree(3) for i in range(10): B.insert_key((i, 2 * i)) B.print_tree(B.root) if B.search_key(8) is not None: print("Found") else: print("Not found") if __name__ == '__main__': main()   
 // Searching a key on a B-tree in Java public class BTree ( private int T; // Node creation public class Node ( int n; int key() = new int(2 * T - 1); Node child() = new Node(2 * T); boolean leaf = true; public int Find(int k) ( for (int i = 0; i < this.n; i++) ( if (this.key(i) == k) ( return i; ) ) return -1; ); ) public BTree(int t) ( T = t; root = new Node(); root.n = 0; root.leaf = true; ) private Node root; // Search key private Node Search(Node x, int key) ( int i = 0; if (x == null) return x; for (i = 0; i < x.n; i++) ( if (key < x.key(i)) ( break; ) if (key == x.key(i)) ( return x; ) ) if (x.leaf) ( return null; ) else ( return Search(x.child(i), key); ) ) // Splitting the node private void Split(Node x, int pos, Node y) ( Node z = new Node(); z.leaf = y.leaf; z.n = T - 1; for (int j = 0; j < T - 1; j++) ( z.key(j) = y.key(j + T); ) if (!y.leaf) ( for (int j = 0; j = pos + 1; j--) ( x.child(j + 1) = x.child(j); ) x.child(pos + 1) = z; for (int j = x.n - 1; j>= pos; j--) ( x.key(j + 1) = x.key(j); ) x.key(pos) = y.key(T - 1); x.n = x.n + 1; ) // Inserting a value public void Insert(final int key) ( Node r = root; if (r.n == 2 * T - 1) ( Node s = new Node(); root = s; s.leaf = false; s.n = 0; s.child(0) = r; Split(s, 0, r); insertValue(s, key); ) else ( insertValue(r, key); ) ) // Insert the node final private void insertValue(Node x, int k) ( if (x.leaf) ( int i = 0; for (i = x.n - 1; i>= 0 && k  = 0 && k x.key(i)) ( i++; ) ) insertValue(x.child(i), k); ) ) public void Show() ( Show(root); ) // Display private void Show(Node x) ( assert (x == null); for (int i = 0; i < x.n; i++) ( System.out.print(x.key(i) + " "); ) if (!x.leaf) ( for (int i = 0; i < x.n + 1; i++) ( Show(x.child(i)); ) ) ) // Check if present public boolean Contain(int k) ( if (this.Search(root, k) != null) ( return true; ) else ( return false; ) ) public static void main(String() args) ( BTree b = new BTree(3); b.Insert(8); b.Insert(9); b.Insert(10); b.Insert(11); b.Insert(15); b.Insert(20); b.Insert(17); b.Show(); if (b.Contain(12)) ( System.out.println("found"); ) else ( System.out.println("not found"); ) ; ) ) 
// Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode ( int val(MAX + 1), count; struct BTreeNode *link(MAX + 1); ); struct BTreeNode *root; // Create a node struct BTreeNode *createNode(int val, struct BTreeNode *child) ( struct BTreeNode *newNode; newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); newNode->val(1) = val; newNode->count = 1; newNode->link(0) = root; newNode->link(1) = child; return newNode; ) // Insert node void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) ( int j = node->count; while (j> pos) ( node->val(j + 1) = node->val(j); node->link(j + 1) = node->link(j); j--; ) node->val(j + 1) = val; node->link(j + 1) = child; node->count++; ) // Split node void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode) ( int median, j; if (pos> MIN) median = MIN + 1; else median = MIN; *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); j = median + 1; while (j val(j - median) = node->val(j); (*newNode)->link(j - median) = node->link(j); j++; ) node->count = median; (*newNode)->count = MAX - median; if (pos val(node->count); (*newNode)->link(0) = node->link(node->count); node->count--; ) // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) ( int pos; if (!node) ( *pval = val; *child = NULL; return 1; ) if (val val(1)) ( pos = 0; ) else ( for (pos = node->count; (val val(pos) && pos> 1); pos--) ; if (val == node->val(pos)) ( printf("Duplicates are not permitted"); return 0; ) ) if (setValue(val, pval, node->link(pos), child)) ( if (node->count < MAX) ( insertNode(*pval, pos, node, *child); ) else ( splitNode(*pval, pval, pos, node, *child, child); return 1; ) ) return 0; ) // Insert the value void insert(int val) ( int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); ) // Search node void search(int val, int *pos, struct BTreeNode *myNode) ( if (!myNode) ( return; ) if (val val(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (val val(*pos) && *pos> 1); (*pos)--) ; if (val == myNode->val(*pos)) ( printf("%d is found", val); return; ) ) search(val, pos, myNode->link(*pos)); return; ) // Traverse then nodes void traversal(struct BTreeNode *myNode) ( int i; if (myNode) ( for (i = 0; i count; i++) ( traversal(myNode->link(i)); printf("%d ", myNode->val(i + 1)); ) traversal(myNode->link(i)); ) ) int main() ( int val, ch; insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18); insert(20); insert(23); traversal(root); printf(""); search(11, &ch, root); )
// Searching a key on a B-tree in C++ #include using namespace std; class TreeNode ( int *keys; int t; TreeNode **C; int n; bool leaf; public: TreeNode(int temp, bool bool_leaf); void insertNonFull(int k); void splitChild(int i, TreeNode *y); void traverse(); TreeNode *search(int k); friend class BTree; ); class BTree ( TreeNode *root; int t; public: BTree(int temp) ( root = NULL; t = temp; ) void traverse() ( if (root != NULL) root->traverse(); ) TreeNode *search(int k) ( return (root == NULL) ? NULL : root->search(k); ) void insert(int k); ); TreeNode::TreeNode(int t1, bool leaf1) ( t = t1; leaf = leaf1; keys = new int(2 * t - 1); C = new TreeNode *(2 * t); n = 0; ) void TreeNode::traverse() ( int i; for (i = 0; i traverse(); cout << " " 
 search(k); ) void BTree::insert(int k) ( if (root == NULL) ( root = new TreeNode(t, true); root->keys(0) = k; root->n = 1; ) else ( if (root->n == 2 * t - 1) ( TreeNode *s = new TreeNode(t, false); s->C(0) = root; s->splitChild(0, root); int i = 0; if (s->keys(0) C(i)->insertNonFull(k); root = s; ) else root->insertNonFull(k); ) ) void TreeNode::insertNonFull(int k) ( int i = n - 1; if (leaf == true) ( while (i>= 0 && keys(i)> k) ( keys(i + 1) = keys(i); i--; ) keys(i + 1) = k; n = n + 1; ) else ( while (i>= 0 && keys(i)> k) i--; if (C(i + 1)->n == 2 * t - 1) ( splitChild(i + 1, C(i + 1)); if (keys(i + 1) insertNonFull(k); ) ) void TreeNode::splitChild(int i, TreeNode *y) ( TreeNode *z = new TreeNode(y->t, y->leaf); z->n = t - 1; for (int j = 0; j keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j C(j) = y->C(j + t); ) y->n = t - 1; for (int j = n; j>= i + 1; j--) C(j + 1) = C(j); C(i + 1) = z; for (int j = n - 1; j>= i; j--) keys(j + 1) = keys(j); keys(i) = y->keys(t - 1); n = n + 1; ) int main() ( BTree t(3); t.insert(8); t.insert(9); t.insert(10); t.insert(11); t.insert(15); t.insert(16); t.insert(17); t.insert(18); t.insert(20); t.insert(23); cout << "The B-tree is: "; t.traverse(); int k = 10; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; k = 2; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; )

Mencari Kompleksitas di Pohon B.

Kasus terburuk Kompleksitas waktu: Θ(log n)

Kasus rata-rata Kompleksitas waktu: Θ(log n)

Kasus terbaik Kompleksitas waktu: Θ(log n)

Kasus rata-rata Kompleksitas ruang: Θ(n)

Kasus terburuk Kompleksitas ruang: Θ(n)

Aplikasi Pohon B

  • database dan sistem file
  • untuk menyimpan blok data (media penyimpanan sekunder)
  • pengindeksan bertingkat

Artikel yang menarik...