definisi
Dalam ilmu komputer, b-tree adalah pohon yang menyeimbangkan diri yang menyimpan data. Struktur data ini memungkinkan pencarian data, akses berurutan, memasukkan data dan menghapus operasi untuk diselesaikan dalam waktu logaritmik.
Mengapa Memperkenalkan B-Tree?
Pertama -tama, termasuk pohon merah dan hitam yang kami perkenalkan sebelumnya, adalah pohon pencarian internal yang menyimpan input ke dalam memori .
B-tree adalah perpanjangan dari algoritma pohon keseimbangan sebelumnya. Ini mendukung pencarian eksternal untuk tabel simbol yang disimpan di disk atau jaringan . File -file ini mungkin jauh lebih besar dari input yang kami pertimbangkan sebelumnya (sulit disimpan dalam memori).
Karena konten disimpan di disk, disk I/O disk terlalu sering dibaca dan ditulis terlalu sering karena kedalaman pohon yang besar (laju pembacaan dan penulisan disk terbatas), yang mengarah pada efisiensi kueri yang tidak efisien.
Maka secara alami penting untuk mengurangi kedalaman pohon. Oleh karena itu, kami memperkenalkan pohon-B, pohon pencarian ganda.
Fitur
Setiap simpul di pohon mengandung paling banyak anak -anak (m> = 2);
Kecuali untuk simpul akar dan simpul daun, setiap node memiliki setidaknya [ceil (m/2)] anak -anak (di mana ceil (x) adalah fungsi yang mengambil batas atas);
Jika simpul akar bukan simpul daun, akan ada setidaknya 2 anak (kasus khusus: tidak ada simpul akar untuk anak -anak, yaitu, simpul akar adalah simpul daun, dan seluruh pohon hanya memiliki satu simpul akar);
Semua node daun muncul di lapisan yang sama (lapisan bawah), dan node daun adalah node eksternal, yang menyimpan konten, yaitu kunci dan nilai .
Node lainnya adalah node internal, yang menyimpan indeks, yaitu kunci dan berikutnya .
Kata kunci node internal: k [1], k [2], ..., k [m-1]; dan k [i] <k [i+1];
Pointer di sebelah node konten: p [1], p [2], ..., p [m]; di mana p [1] menunjuk ke subtree dengan kata kunci kurang dari k [1], p [m] menunjuk ke subtree dengan kata kunci yang lebih besar dari k [m-1], dan p [i] lainnya menunjuk ke subtree dengan kata kunci (k [i-1], k [i]);
Misalnya: (m = 3)
Temukan dan masukkan
Untuk kenyamanan, kunci sentinel khusus digunakan di sini, yang lebih kecil dari semua kunci lainnya dan diwakili oleh *.
Pada awalnya, b-tree hanya berisi satu node akar, dan simpul akar hanya berisi kunci sentinel saat diinisialisasi.
Setiap kunci dalam simpul internal dikaitkan dengan node. Semua tombol lebih besar dari atau sama dengan kunci yang terkait dengan node ini, tetapi lebih kecil dari semua kunci lainnya.
Konvensi ini dapat sangat menyederhanakan kode.
Kode
Klik untuk mengunduh.
Implementasi kode ini memperkenalkan kunci sentinel, dan output kode menghilangkannya.
B-tree dengan kunci sentinel dalam kode (simpan gambar secara lokal untuk dilihat, dan kata-kata akan lebih jelas):
Output b-tree oleh kode (simpan gambar secara lokal untuk dilihat, dan kata-kata akan lebih jelas):
Kelas Publik BTREE <Key memperluas <Y key>, value> {// Max Children per b-tree node = m-1 // (harus genap dan lebih besar dari 2) int m = 4 private static final m = 4; root simpul pribadi; // root dari tinggi int private b-tree; // tinggi int n-tree private int n; // Jumlah pasangan nilai-kunci di b-tree // helper b-tree node tipe data private static class final node {private int m; // jumlah anak -anak entri pribadi [] anak -anak = entri baru [m]; // Array anak -anak // Buat simpul dengan k Children Private Node (int k) {m = k; }} // node internal: Hanya gunakan tombol dan berikutnya // node eksternal: Hanya gunakan kunci dan nilai entri kelas statis privat {pribadi yang sebanding dengan kunci; objek pribadi val; node pribadi selanjutnya; // Field Helper To Itererate Over Array Entries Entri Publik (Kunci yang sebanding, Objek Val, Node Next) {this.key = key; this.val = val; this.next = next; }} /*** Menginisialisasi b-tree kosong. */ public btree () {root = node baru (0); } /*** Mengembalikan true jika tabel simbol ini kosong. * @return {@code true} Jika tabel simbol ini kosong; {@code false} sebaliknya */ public boolean isEmpty () {return size () == 0; } /*** Mengembalikan jumlah pasangan nilai kunci dalam tabel simbol ini. * @return Jumlah pasangan nilai kunci dalam tabel simbol ini */ ukuran int int () {return n; } /*** Mengembalikan ketinggian b-tree ini (untuk debugging). * * @return ketinggian b-tree */ public int height () {return height; } /*** Mengembalikan nilai yang terkait dengan kunci yang diberikan. * * Kunci @param Kunci * @return Nilai yang terkait dengan kunci yang diberikan jika kunci ada di tabel simbol * dan {@code null} jika kunci tidak ada di tabel simbol * @throws nullpointerException jika {@code kunci tidak ada {@code null} */ nilai publik get (kunci key) {if noT (key == null) {null) {noulce) get (kunci) {@code if (key == null) {null) {noulce noule) {noule noule (tombol noule) {noule noule) {noule noule) get (kunci) {@code if (key == null) {@code null { } return Search (root, kunci, tinggi); } @SuppressWarnings ("Uncecked") Private Value Search (Node X, Key Key, int ht) {entri [] anak -anak = x.children; // simpul eksternal ke simpul daun terendah, traverse if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (kunci, anak -anak [j] .key)) {return (value) anak -anak [j] .val; }}} // Node internal secara rekursif mencari alamat lain berikutnya {for (int j = 0; j <xm; j ++) {if (j+1 == xm || kurang (kunci, anak-anak [j+1] .key)) {return Search (anak-anak [j] .next, kunci, ht-1); }}} return null; } /** * Memasukkan pasangan nilai kunci ke dalam tabel simbol, menimpa nilai lama * dengan nilai baru jika kunci sudah ada di tabel simbol. * Jika nilainya {@code null}, ini secara efektif menghapus kunci dari tabel simbol. * * @param Key Kunci * @param val Nilai * @throws nullpointerException if {@code Key} adalah {@code null} */ public void put (tombol tombol, val val) {if (key == null) {lempar nullpointerException baru ("Key tidak boleh menjadi null"); } Node u = masukkan (root, kunci, val, tinggi); // simpul kanan yang dihasilkan setelah split n ++; if (u == null) {return; } // perlu membagi node root reorganisasi root T = node baru (2); t.children [0] = entri baru (root.Children [0] .key, null, root); t.children [1] = entri baru (U.Children [0] .Key, null, u); root = t; tinggi ++; } private node insert (node h, tombol kunci, nilai val, int ht) {int j; Entri t = entri baru (kunci, val, null); // simpul eksternal simpul eksternal, yang juga merupakan simpul daun. Di bagian bawah pohon, nilai konten disimpan if (ht == 0) {for (j = 0; j <hm; j ++) {if (kurang (key, h.children [j] .key)) {break; }}} // simpul internal di dalam simpul adalah alamat berikutnya {for (j = 0; j <hm; j ++) {if ((j+1 == hm) || lebih sedikit (tombol, h.Children [j+1] .Key)) {node u = insert (h.Children [j ++]. if (u == null) {return null; } t.key = u.children [0] .key; t.next = u; merusak; }}} untuk (int i = hm; i> j; i--) {h.children [i] = h.children [i-1]; } H.Children [j] = t; H.M ++; if (hm <m) {return null; } else {// split node return split (h); }} // split node di setengah node private split (simpul h) {node t = node baru (m/2); hm = m/2; untuk (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } return t; } /*** Mengembalikan representasi string dari b-tree ini (untuk debugging). * * @return representasi string dari b-tree ini. */ public string toString () {return tostring (root, height, "") + "/ n"; } private string toString (node h, int ht, string indent) {stringBuilder s = new stringBuilder (); Entri [] anak -anak = H.Children; if (ht == 0) {for (int j = 0; j <hm; j ++) {S.Append (indent + anak -anak [j] .key + "" + anak -anak [j] .val + "/n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {s.Append (indent + "(" + anak -anak [j] .key + ")/n"); } s. lampai (tostring (anak-anak [j] .next, ht-1, indent + "")); }} return s.toString (); } // Fungsi Perbandingan - Buat sebanding, bukan kunci untuk menghindari casts private boolean lebih sedikit (K1 yang sebanding, K2 yang sebanding) {return k1.compareto (k2) <0; } private boolean eq (sebanding k1, sebanding k2) {return k1.compareto (k2) == 0; } /*** Unit menguji {@code btree} tipe data. * * @param argumen argumen baris perintah */ public static void main (string [] args) {btree <string, string> st = btree <string, string> () baru; St.put ("www.cs.princeton.edu", "128.112.136.12"); St.put ("www.cs.princeton.edu", "128.112.136.11"); St.put ("www.princeton.edu", "128.112.128.15"); St.put ("www.yale.edu", "130.132.143.21"); St.put ("www.simpsons.com", "209.052.165.60"); St.put ("www.apple.com", "17.112.152.32"); St.put ("www.amazon.com", "207.171.182.16"); St.put ("www.ebay.com", "66.135.192.87"); St.put ("www.cnn.com", "64.236.16.20"); St.put ("www.google.com", "216.239.41.99"); St.put ("www.nytimes.com", "199.239.136.200"); St.put ("www.microsoft.com", "207.126.99.140"); St.put ("www.dell.com", "143.166.224.230"); St.put ("www.slashdot.org", "66.35.250.151"); St.put ("www.espn.com", "199.181.135.201"); St.put ("www.weather.com", "63.111.66.11"); St.put ("www.yahoo.com", "216.109.118.65"); System.out.println ("cs.princeton.edu:" + st.get ("www.cs.princeton.edu")); System.out.println ("hardvarducks.com:" + st.get ("www.harvarduckscucks.com")); System.out.println ("Simpsons.com:" + St.Get ("www.simpsons.com")); System.out.println ("Apple.com:" + St.Get ("www.apple.com")); System.out.println ("ebay.com:" + St.Get ("www.ebay.com")); System.out.println ("dell.com:" + st.get ("www.dell.com")); System.out.println ("Ukuran:" + St.Size ()); System.out.println ("Tinggi:" + St.Height ()); System.out.println (ST); System.out.println (); }} Keluaran:
cs.princeton.edu: 128.112.136.12
Hardvarducks.com: Null
Simpsons.com: 209.052.165.60
Apple.com: 17.112.152.32
eBay.com: 66.135.192.87
dell.com: 143.166.224.230
Ukuran: 17
Tinggi: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.