B medis

Šioje pamokoje sužinosite, kas yra B medis. Taip pat rasite veikiančių paieškos operacijų B medyje C, C ++, Java ir Python pavyzdžius.

B medis yra specialus savaime balansuojančio paieškos medžio tipas, kuriame kiekvienas mazgas gali turėti daugiau nei vieną raktą ir turėti daugiau nei du vaikus. Tai apibendrinta dvejetainio paieškos medžio forma.

Jis taip pat žinomas kaip aukščio subalansuotas m-way medis.

B medis

Kodėl B medis?

„B-tree“ poreikis atsirado dėl to, kad reikia mažiau laiko pasiekti fizinę laikmeną kaip kietąjį diską. Antriniai kaupikliai yra lėtesni, turintys didesnę talpą. Reikėjo tokio tipo duomenų struktūrų, kurios sumažintų prieigą prie disko.

Kitos duomenų struktūros, tokios kaip dvejetainis paieškos medis, AVL medis, raudonai juodas medis ir kt., Viename mazge gali laikyti tik vieną raktą. Jei turite laikyti daug raktų, tokių medžių aukštis tampa labai didelis, o prieigos laikas ilgėja.

Tačiau „B-tree“ gali laikyti daug raktų viename mazge ir gali turėti kelis antrinius mazgus. Tai žymiai sumažina aukštį ir leidžia greičiau pasiekti diską.

B medžio savybės

  1. Kiekvieno mazgo x raktai saugomi didėjančia tvarka.
  2. Kiekviename mazge yra loginė reikšmė x.leaf, kuri yra teisinga, jei x yra lapas.
  3. Jei n yra medžio tvarka, kiekviename vidiniame mazge gali būti ne daugiau kaip n - 1 raktai ir kiekvieno vaiko rodyklė.
  4. Kiekviename mazge, išskyrus šaknį, gali būti ne daugiau kaip n vaikas ir mažiausiai n / 2 vaikai.
  5. Visų lapų gylis yra vienodas (ty medžio aukštis-h).
  6. Šaknyje yra mažiausiai 2 vaikai ir joje yra bent 1 raktas.
  7. Jei n ≧ 1, tada bet n-raktas B-medis aukščio h ir minimalų t ≧ 2, .h ≧ logt (n+1)/2

Operacijos

Ieškoma

Elemento paieška B medyje yra apibendrinta elemento paieškos forma Dvejetainiame paieškos medyje. Atliekami šie veiksmai.

  1. Pradėdami nuo šakninio mazgo, palyginkite k su pirmuoju mazgo raktu.
    Jei k = the first key of the node, grąžinkite mazgą ir indeksą.
  2. Jei k.leaf = true, grąžinkite NULL (ty nerasta).
  3. Jei k < the first key of the root node, ieškokite kairiajame šio rakto tekste rekursyviai.
  4. Jei dabartiniame mazge yra daugiau nei vienas raktas k> the first key, palyginkite k su kitu mazgo raktu.
    Jei k < next key, ieškokite kairiajame šio rakto tekste (t. Y. K yra tarp pirmojo ir antrojo klavišų).
    Kitu atveju ieškokite tinkamo rakto vaiko.
  5. Pakartokite 1–4 veiksmus, kol pasieks lapą.

Paieškos pavyzdys

  1. Paieškokime raktą k = 17medyje žemiau 3 laipsnio. B medis
  2. k nėra šaknyje, todėl palyginkite jį su šakniniu raktu. k nėra šaknies mazge
  3. Nuo tada k> 11eikite į tinkamą šaknies mazgo vaiką. Eikite į dešinį potemį
  4. Palyginkite k su 16. Nuo tada k> 16palyginkite k su kitu mygtuku 18. Palyginkite su klavišais iš kairės į dešinę
  5. Kadangi k < 18, k yra nuo 16 iki 18, ieškokite dešiniojo 16 metų vaiko ar kairio 18 vaiko. K yra tarp 16 ir 18
  6. rastas k. rastas k

Elemento paieškos 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)

Norėdami sužinoti daugiau apie įvairias B medžio operacijas, apsilankykite

  • Įterpimas ant B medžio
  • Ištrynimas iš B medžio

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Ieškoma sudėtingumo B medyje

Blogiausias atvejo sudėtingumas: Θ(log n)

Vidutinis atvejo sudėtingumas: Θ(log n)

Geriausias atvejo sudėtingumas: Θ(log n)

Vidutinis atvejis Erdvės sudėtingumas: Θ(n)

Blogiausias kosmoso sudėtingumas: Θ(n)

B medžių programos

  • duomenų bazės ir bylų sistemos
  • saugoti duomenų blokus (antrinės laikmenos)
  • daugiapakopis indeksavimas

Įdomios straipsniai...