B ağacı

Bu eğitimde B-ağacının ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bir B ağacında arama işleminin çalışma örneklerini bulacaksınız.

B-ağacı, her bir düğümün birden fazla anahtar içerebileceği ve ikiden fazla çocuğa sahip olabileceği özel bir kendi kendini dengeleyen arama ağacı türüdür. İkili arama ağacının genelleştirilmiş bir şeklidir.

Aynı zamanda yüksekliği dengeli bir m-yollu ağaç olarak da bilinir.

B ağacı

Neden B-ağacı?

B-ağacına duyulan ihtiyaç, bir sabit disk gibi fiziksel depolama ortamına erişimde daha az zamana duyulan ihtiyacın artmasıyla ortaya çıktı. İkincil depolama cihazları, daha büyük kapasiteyle daha yavaştır. Disk erişimlerini en aza indiren bu tür veri yapılarına ihtiyaç vardı.

İkili arama ağacı, avl ağacı, kırmızı-siyah ağaç vb. Gibi diğer veri yapıları bir düğümde yalnızca bir anahtar depolayabilir. Çok sayıda anahtar saklamanız gerekiyorsa, bu tür ağaçların yüksekliği çok büyür ve erişim süresi artar.

Bununla birlikte, B-tree birçok anahtarı tek bir düğümde saklayabilir ve birden çok alt düğüme sahip olabilir. Bu, yüksekliği önemli ölçüde azaltır ve daha hızlı disk erişimine izin verir.

B-ağaç Özellikleri

  1. Her bir x düğümü için, anahtarlar artan sırada depolanır.
  2. Her düğümde, x bir yapraksa doğru olan bir boole değeri x.leaf vardır.
  3. Ağacın sırası n ise, her dahili düğüm en fazla n - 1 anahtar ve her alt öğe için bir gösterici içerebilir.
  4. Kök dışındaki her düğümün en fazla n çocuğu ve en az n / 2 çocuğu olabilir.
  5. Tüm yapraklar aynı derinliğe sahiptir (yani ağacın yüksekliği-h).
  6. Kökün en az 2 alt öğesi vardır ve en az 1 anahtar içerir.
  7. N ≧ 1 ise, o zaman, h yüksekliği ve en az derece herhangi bir n, anahtar B-ağacı t ≧ 2, .h ≧ logt (n+1)/2

Operasyonlar

Aranıyor

Bir B-ağacında bir elemanın aranması, İkili Arama Ağacındaki bir elemanı aramanın genelleştirilmiş şeklidir. Aşağıdaki adımlar takip edilir.

  1. Kök düğümden başlayarak, k ile düğümün ilk anahtarını karşılaştırın.
    If k = the first key of the node, düğümü ve dizini döndürün.
  2. Eğer k.leaf = true, NULL döndürür (yani bulunamadı).
  3. Eğer k < the first key of the root node, bu anahtarın sol çocuğunu yinelemeli olarak arayın.
  4. Geçerli düğümde birden fazla anahtar varsa ve düğümdeki bir k> the first keysonraki anahtar ile k'yi karşılaştırın.
    Eğer k < next key, bu tuşun sol çocuğunu arayın (yani, k birinci ve ikinci tuşlar arasında bulunur).
    Aksi takdirde, anahtarın doğru çocuğunu arayın.
  5. Yaprağa ulaşılana kadar 1'den 4'e kadar olan adımları tekrarlayın.

Arama Örneği

  1. k = 173. derecenin altındaki ağaçta anahtarı arayalım . B-ağacı
  2. k kökte bulunmadığından kök anahtarla karşılaştırın. k kök düğümde bulunamadı
  3. O zamandan beri k> 11, kök düğümün doğru çocuğuna gidin. Sağ alt ağaca git
  4. K'yi 16 ile karşılaştırın. Çünkü k> 16, k'yi sonraki anahtar 18 ile karşılaştırın. Soldan sağa doğru tuşlarla karşılaştırın.
  5. k < 18K, 16 ile 18 arasında olduğu için , 16'nın sağ çocuğunda veya 18'in sol çocuğunda arama 16 ile 18 arasında yer almaktadır.
  6. k bulunur. k bulundu

Bir Eleman Arama Algoritması

 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)

Farklı B-ağacı işlemleri hakkında daha fazla bilgi edinmek için lütfen şu adresi ziyaret edin:

  • B-ağacına ekleme
  • B ağacında silme

Python, Java ve C / C ++ Örnekleri

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"; )

B Ağacında Karmaşıklık Arama

En kötü durum Zaman karmaşıklığı: Θ(log n)

Ortalama vaka Zaman karmaşıklığı: Θ(log n)

En iyi durum Zaman karmaşıklığı: Θ(log n)

Ortalama durum Uzay karmaşıklığı: Θ(n)

En kötü durum Uzay karmaşıklığı: Θ(n)

B Ağaç Uygulamaları

  • veritabanları ve dosya sistemleri
  • veri bloklarını depolamak için (ikincil depolama ortamı)
  • çok düzeyli indeksleme

Ilginç makaleler...