B-drevo

V tej vadnici boste izvedeli, kaj je B-drevo. Prav tako boste našli delovne primere iskanja na B-drevesu v C, C ++, Java in Python.

B-drevo je posebna vrsta samo uravnoteževalnega drevesa iskanja, v katerem lahko vsako vozlišče vsebuje več kot en ključ in ima lahko več kot dva otroka. Je posplošena oblika binarnega drevesa iskanja.

Znano je tudi kot višinsko uravnoteženo drevo m.

B-drevo

Zakaj B-drevo?

Potreba po B-drevesu se je pojavila z naraščanjem potrebe po krajšem času dostopa do fizičnega pomnilniškega medija, kot je trdi disk. Sekundarne naprave za shranjevanje so počasnejše z večjo zmogljivostjo. Potrebne so bile takšne vrste podatkovnih struktur, ki zmanjšujejo dostop do diska.

Druge podatkovne strukture, kot so binarno drevo iskanja, drevo avl, rdeče-črno drevo itd., Lahko shranijo samo en ključ v enem vozlišču. Če morate shraniti veliko število ključev, potem višina takšnih dreves postane zelo velika in čas dostopa se poveča.

Vendar lahko B-drevo shrani veliko ključev v enem vozlišču in ima lahko več podrejenih vozlišč. To znatno zmanjša višino, kar omogoča hitrejši dostop do diska.

Lastnosti B-drevesa

  1. Za vsako vozlišče x so ključi shranjeni v naraščajočem vrstnem redu.
  2. V vsakem vozlišču je logična vrednost x.leaf, ki je resnična, če je x list.
  3. Če je n vrstni red drevesa, lahko vsako notranje vozlišče vsebuje največ n - 1 ključev skupaj s kazalcem na vsakega otroka.
  4. Vsako vozlišče razen korena ima lahko največ n otrok in vsaj n / 2 otrok.
  5. Vsi listi imajo enako globino (tj. Višina-h drevesa).
  6. Koren ima vsaj 2 otroka in vsebuje najmanj 1 ključ.
  7. Če je n ≧ 1, nato pa za vsako n-ključ B-drevesa višine h in najmanjšo stopnjo t ≧ 2, .h ≧ logt (n+1)/2

Operacije

Iskanje

Iskanje elementa v B-drevesu je splošna oblika iskanja elementa v binarnem drevesu iskanja. Sledijo naslednji koraki.

  1. Od korenskega vozlišča primerjajte k s prvim ključem vozlišča.
    Če k = the first key of the node, vrnite vozlišče in indeks.
  2. Če k.leaf = truevrne NULL (tj. Ni najdeno).
  3. Če k < the first key of the root node, rekurzivno poiščite levega podrejenega ključa.
  4. Če je v trenutnem vozlišču več kot en ključ in k> the first key, primerjajte k z naslednjim ključem v vozlišču.
    Če k < next key, poiščite levega podrejenega ključa (tj. K leži med prvo in drugo tipko).
    V nasprotnem primeru poiščite pravega otroka ključa.
  5. Ponavljajte korake od 1 do 4, dokler ne dosežete lista.

Primer iskanja

  1. Poiščimo ključ za iskanje k = 17v drevesu pod stopnjo 3. B-drevo
  2. k ni v korenu, zato ga primerjajte s korenskim ključem. k ni mogoče najti v korenskem vozlišču
  3. Ker k> 11pojdite na desnega otroka korenskega vozlišča. Pojdite na desno poddrevo
  4. Primerjaj k s 16. Ker k> 16primerjaj k z naslednjo tipko 18. Primerjaj s tipkami od leve proti desni
  5. Ker k < 18je k med 16 in 18. Poiščite desnega otroka 16 ali levega otroka 18 let. K leži med 16 in 18
  6. k je najden. k je najden

Algoritem za iskanje elementa

 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)

Če želite izvedeti več o različnih operacijah dreves B, obiščite

  • Vstavitev na B-drevo
  • Izbris na B-drevesu

Primeri Python, Java in 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"; )

Iskanje kompleksnosti na drevesu B

Najslabši čas Zapletenost: Θ(log n)

Povprečna zapletenost primera: Θ(log n)

Najboljši primer Časovna zapletenost: Θ(log n)

Povprečna zapletenost prostora: Θ(n)

Najslabši primer Zapletenost prostora: Θ(n)

B drevesne aplikacije

  • baze podatkov in datotečni sistemi
  • za shranjevanje blokov podatkov (sekundarni pomnilniški medij)
  • indeksiranje na več ravneh

Zanimive Članki...