B-pokok

Dalam tutorial ini, anda akan belajar apa itu pohon B. Anda juga akan dapati contoh operasi operasi carian di pohon B di C, C ++, Java dan Python.

B-tree adalah jenis pokok carian keseimbangan diri khas di mana setiap nod boleh mengandungi lebih daripada satu kunci dan boleh mempunyai lebih daripada dua anak. Ini adalah bentuk umum dari carian pokok binari.

Ia juga dikenali sebagai pokok m-way yang seimbang tinggi.

B-pokok

Mengapa pokok B?

Keperluan untuk B-tree muncul dengan meningkatnya keperluan untuk waktu yang lebih sedikit dalam mengakses media penyimpanan fizikal seperti cakera keras. Peranti simpanan sekunder lebih perlahan dengan kapasiti yang lebih besar. Terdapat keperluan untuk jenis struktur data yang meminimumkan akses cakera.

Struktur data lain seperti pokok carian binari, pohon avl, pohon merah-hitam, dan lain-lain boleh menyimpan hanya satu kunci dalam satu nod. Sekiranya anda perlu menyimpan sebilangan besar kunci, maka ketinggian pokok seperti itu menjadi sangat besar dan masa akses meningkat.

Walau bagaimanapun, B-tree dapat menyimpan banyak kunci dalam satu nod dan boleh mempunyai beberapa nod anak. Ini mengurangkan ketinggian dengan ketara membolehkan akses cakera lebih cepat.

Harta B-pokok

  1. Untuk setiap nod x, kunci disimpan mengikut urutan.
  2. Di setiap simpul, terdapat nilai boolean x.leaf yang benar jika x adalah daun.
  3. Sekiranya n adalah urutan pokok, setiap simpul dalaman boleh memuat paling banyak kunci n - 1 bersama dengan penunjuk kepada setiap anak.
  4. Setiap nod kecuali root boleh mempunyai paling banyak n kanak-kanak dan sekurang-kurangnya n / 2 anak.
  5. Semua daun mempunyai kedalaman yang sama (iaitu tinggi-h pokok).
  6. Akarnya mempunyai sekurang-kurangnya 2 anak dan mengandungi minimum 1 kunci.
  7. Jika n ≧ 1, maka bagi mana-mana n-key B-pohon h ketinggian dan tahap minimum t ≧ 2, .h ≧ logt (n+1)/2

Operasi

Mencari

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

  1. Bermula dari simpul root, bandingkan k dengan kunci pertama nod.
    Sekiranya k = the first key of the node, kembalikan nod dan indeks.
  2. Sekiranya k.leaf = true, kembalikan NULL (iaitu tidak dijumpai).
  3. Sekiranya k < the first key of the root node, cari anak kiri kunci ini secara berulang.
  4. Sekiranya terdapat lebih daripada satu kunci dalam nod semasa dan k> the first key, bandingkan k dengan kekunci seterusnya dalam nod.
    Jika k < next key, cari anak kiri kunci ini (mis. K terletak di antara kekunci pertama dan kedua).
    Jika tidak, cari anak kunci yang betul.
  5. Ulangi langkah 1 hingga 4 sehingga daun dicapai.

Mencari Contoh

  1. Mari kita cari kunci k = 17di bawah pokok darjah 3. B-tree
  2. k tidak dijumpai di akar jadi, bandingkan dengan kunci akar. k tidak dijumpai pada nod akar
  3. Sejak k> 11, pergi ke anak kanan simpul akar. Pergi ke subtree kanan
  4. Bandingkan k dengan 16. Sejak k> 16, bandingkan k dengan kekunci seterusnya 18. Bandingkan dengan kekunci dari kiri ke kanan
  5. Sejak 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 dijumpai. k dijumpai

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 mengetahui lebih lanjut mengenai operasi B-tree yang berbeza, sila lawati

  • Penyisipan pada pokok B
  • Penghapusan pada pokok B

Contoh Python, Java dan C / C ++

Python Java C 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 Kerumitan di Pokok B

Kerumitan masa terburuk: Θ(log n)

Kerumitan masa kes purata: Θ(log n)

Kerumitan masa kes terbaik: Θ(log n)

Kerumitan ruang kes rata-rata: Θ(n)

Kerumitan ruang terburuk: Θ(n)

Aplikasi Pokok B

  • pangkalan data dan sistem fail
  • untuk menyimpan blok data (media simpanan sekunder)
  • pengindeksan pelbagai peringkat

Artikel menarik...