English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
تعريف
في علوم الكمبيوتر، شجرة B (بالإنجليزية: B-tree) هي شجرة متوازنة ذاتية، يمكنها الحفاظ على البيانات منظمًا. يمكن لهذه بنية البيانات إكمال العمليات مثل البحث عن البيانات والوصول الوردي والتعديل والإزالة في وقت معاملات اللوغاريتم.
لماذا نحتاج إلى شجرة B?
أولاً، بما في ذلك الأشجار السوداء والأحمر التي قمنا بشرحها سابقًا، يتم حفظ المدخلات فيالذاكرةنوعشجرة البحث الداخلية.
أما شجرة B فهي توسيع لخوارزميات الشجرة المتوازنة السابقة، وتدعم الحفظ فيالقرص أو الشبكةللإشارات إلى جدول الأسماءالبحث الخارجي، قد تكون هذه الملفات أكبر بكثير من تلك التي كنا نفكر فيها من قبل (من الصعب حفظها في الذاكرة)
لأن المحتوى يتم حفظه على القرص الصلب، فإنه سيكون طبيعياً أن يكون هناك تردد عالي جدًا في قراءة و كتابة وحدات المعالجة المركزية (السرعة التي يمكنها القرص الصلب هي محدودة)، مما يؤدي إلى انخفاض كفاءة البحث.
لذلك، من الطبيعي أن يكون خفض عمق الشجرة مهمًا جدًا. لذا، قمنا بإدخال شجرة B، شجرة البحث المتعدد
ميزات
شجرة كل عقدة تحتوي على على الأكثر m أطفال (m>=2)
إلا إذا كانت العقدة الجذور والعقد الأوراق، فإن كل عقدة تحتوي على على الأقل [ceil(m / 2)] أطفال (حيث ceil(x) هو دالة تحديد الأعلى)
إذا لم يكن العقدة الجذور هي العقد الأوراق، فإن لديها على الأقل 2 طفل (حالة خاصة: العقدة الجذور التي ليس لديها أطفال، أي العقدة الجذور هي العقد الأوراق، والشجرة تحتوي على جذور واحدة فقط)
تظهر جميع العقد الأوراق في نفس المستوى (أدنى مستوى)العقد الأوراق هي العقد الخارجية، وتحفظ المحتويات، وهي المفتاح والقيمة.
العقد الأخرى هي العقد الداخلية، وتحفظ الفهارس، وهي المفتاح والنقاط.
المفاتيح في العقدة الداخلية: K[1], K[2], …, K[M-1]؛ وكذلك K[i] < K[i+1]
إشارات النقاط في العقدة المحتوية على المحتويات: P[1], P[2], …, P[M]؛ حيث يوحي P[1] بفرع المفاتيح أقل من K[1]، ويوحي P[M] بفرع المفاتيح أكبر من K[M-1]، وكل P[i] يوحي بفرع المفاتيح تتباين بين (K[i-1], K[i])
على سبيل المثال: (M=3)
البحث والإدراج
لإيجاد راحة، تم استخدام مفتاح حراسة خاص، وهو أصغر من جميع المفاتيح الأخرى، ويتم تمثيله بـ*
بداية، تحتوي شجرة B فقط على عقدة جذور، والتي تحتوي على مفتاح حراسة فقط عند التشغيل
كل مفتاح في العقدة الداخلية مرتبط بجزء من العقدة، والذي يكون الجذر بهذا الجزء هو شجرة الفرع، حيث تكون جميع المفاتيح أكبر أو تساوي المفتاح المرتبط بهذا الجزء، ولكن أقل من جميع المفاتيح الأخرى
هذه الاتفاقات يمكن أن تبسط الكود بشكل كبير
الكود
انقر للتحميل
يقدم هذا الكود مفتاح حراسة، ولكن يتم إزالته من الناتج
شجرة B التي تحتوي على مفتاح حراسة في الكود (حفظ الصورة على الجهاز للحصول على وضوح أكبر)
شجرة B التي يتم إخراجها من الكود (حفظ الصورة على الجهاز للحصول على وضوح أكبر)
public class BTree<Key extends Comparable<Key>, Value>
{
// أقصى عدد من الأطفال لكل عقدة في شجرة B = M-1
// (يجب أن يكون زوجياً وأكبر من 2)
private static final int M = 4;
private Node root; // جذور شجرة B
private int height; // ارتفاع شجرة B
private int n; // عدد الأزواج المفتاح-القيمة في شجرة B
// helper B-tree node data type
private static final class Node
{
private int m; // number of children
private Entry[] children = new Entry[M]; // the array of children
// create a node with k children
private Node(int k)
{
m = k;
}
}
// internal nodes: only use key and next
// external nodes: only use key and value
private static class Entry
{
private Comparable key;
private Object val;
private Node next; // helper field to iterate over array entries
public Entry(Comparable key, Object val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty B-tree.
*/
public BTree()
{
root = new Node(0);
}
/**
* Returns true if this symbol table is empty.
* @return {@code true} if this symbol table is empty; {@code false} otherwise
*/
public boolean isEmpty()
{
return size() == 0;
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size()
{
return n;
}
/**
* يعود طول هذا الشجرة الثنائية (لإجراء الت调试).
*
* @return طول هذا الشجرة الثنائية
*/
public int height()
{
return height;
}
/**
* يعود القيمة المرتبطة بالكلاء المحدد.
*
* @param key الكلاء
* @return القيمة المرتبطة بالكلاء المحدد إذا كان الكلاء في جدول الرموز
* وإذا لم يكن الكلاء في جدول الرموز، فسيكون null
* @throws NullPointerException إذا كان @code key} @code null}
*/
public Value get(Key key)
{
إذا (key == null)
{
throw new NullPointerException("key must not be null");
}
return search(root, key, height);
}
@SuppressWarnings("unchecked")
private Value search(Node x, Key key, int ht)
{
Entry[] children = x.children;
// external node إلى أقصى نقطة في الشجرة الخضراء، الترحيل
if (ht == 0)
{
for (int j = 0; j < x.m; j++)
{
if (eq(key, children[j].key))
{
return (Value) children[j].val;
}
}
}
// internal node البحث التكراري عن عنوان التالي
else
{
for (int j = 0; j < x.m; j++)
{
if (j+1 == x.m || less(key, children[j+1].key))
{
return search(children[j].next, key, ht-1);
}
}
}
return null;
}
/**
* يضيف زوج الكلاء-القيمة إلى جدول الرموز، محو القيمة القديمة
* مع القيمة الجديدة إذا كان الكلاء موجودًا في جدول الرموز.
* إذا كان القيمة null، فإن هذا يزيل الكلاء من جدول الرموز بشكل فعلي.
*
* @param key الكلاء
* @param val القيمة
* @throws NullPointerException إذا كان @code key} @code null}
*/
public void put(Key key, Value val)
{
إذا (key == null)
{
throw new NullPointerException("key must not be null");
}
Node u = insert(root, key, val, height); // node اليمين الناتج عن الانقسام
n++;
إذا (u == null)
{
return;
}
// needs to split root重组root
Node t = new Node(2);
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;
height++;
}
private Node insert(Node h, Key key, Value val, int ht)
{
int j;
Entry t = new Entry(key, val, null);
// node خارجي، وهو أيضًا ورقة، في أعمق طبقات الشجرة، يحتوي على values
if (ht == 0)
{
للمحصول على (j = 0; j < h.m; j++)
{
إذا (less(key, h.children[j].key))
{
فجعل;
}
}
}
// node داخلي، يحتوي على addresses التالية
else
{
للمحصول على (j = 0; j < h.m; j++)
{
إذا ((j+1 == h.m) أو less(key, h.children[j+1].key))
{
Node u = insert(h.children[j++].next, key, val, ht-1);
إذا (u == null)
{
return null;
}
t.key = u.children[0].key;
t.next = u;
فجعل;
}
}
}
للمحصول على (i = h.m; i > j; i--)
{
h.children[i] = h.children[i-1];
}
h.children[j] = t;
h.m++;
إذا (h.m < M)
{
return null;
}
else
{ // divide node
return split(h);
}
}
// split node in half
private Node split(Node h)
{
Node t = new Node(M/2);
h.m = M/2;
for (int j = 0; j < M/2; j++)
{
t.children[j] = h.children[M/2+j];
}
return t;
}
/**
* Returns a string representation of this B-tree (for debugging).
*
* @return a string representation of this B-tree.
*/
public String toString()
{
return toString(root, height, "") + "\n";
}
private String toString(Node h, int ht, String indent)
{
StringBuilder s = new StringBuilder();
Entry[] children = h.children;
if (ht == 0)
{
for (int j = 0; j < h.m; j++)
{
s.append(indent + children[j].key + " " + children[j].val + "\n");
}
}
else
{
for (int j = 0; j < h.m; j++)
{
if (j > 0)
{
s.append(indent + "(" + children[j].key + ")\n");
}
s.append(toString(children[j].next, ht-1, indent + " "));
}
}
return s.toString();
}
// functions of comparison - make Comparable instead of Key to avoid casts
private boolean less(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) == 0;
}
/**
* Unit tests the {@code BTree} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args)
{
BTree<String, String> st = new BTree<String, String>();
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("hardvardsucks.com: " + st.get("www.harvardsucks.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();
System.out.println("حجم: " + st.size());
System.out.println("طول: " + st.height());
System.out.println(st);
System.out.println();
}
}
الخروج:
cs.princeton.edu: 128.112.136.12
hardvardsucks.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
حجم: 17
طول: 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
هذا هو نهاية محتوى هذا المقال، نأمل أن يكون قد ساعدكم في التعلم، ونأمل أن تدعموا دائمًا تعليمات الصياح.
البيان: محتويات هذا المقال تم جمعها من الإنترنت، وتعود حقوق الطبع والنشر إلى المالك الأصلي، وقد تم إدراج المحتوى من قبل مستخدمي الإنترنت بطرقهم الخاصة، ولا يمتلك هذا الموقع حقوق الملكية، ولا يتم تعديل المحتوى بشكل إنساني، ولا يتحمل هذا الموقع أي مسؤولية قانونية. إذا رأيت محتوى يشتبه في انتهاك حقوق النسخ، فلا تتردد في إرسال بريد إلكتروني إلى: notice#oldtoolbag.com (عند إرسال البريد الإلكتروني، يرجى استبدال # ب @) لتقديم الشكوى، وتقديم الدليل المتعلق، وسيتم حذف المحتوى المزعوم فور التحقق منه.