درخت بی B-Tree، آموزش درخت b tree

درخت B یا B-tree یک ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است درخت جستجوی باینری است که برای عملیات جستجو و حذف سریع بهینه شده است. در پایگاه‌های داده، سیستم‌های فایل و سایر برنامه‌ها که در آن داده‌های گسترده باید به طور مؤثر جستجو شوند، استفاده می‌شود. B-treeها می‌توانند کلیدها و مقادیر زیادی را در یک فضای فشرده ذخیره کنند و از عملیات‌های درج و حذف سریع پشتیبانی کنند. در این مقاله به بررسی این نوع درختان می‌پردازیم.

ویژگی‌های درخت B

درخت B از مرتبه n شامل تمام ویژگی‌های درخت است، علاوه بر این شامل خواص زیر نیز می‌باشد:

برای هر گره x، کلیدها به ترتیب افزایشی ذخیره می‌شوند.
هر گره یک مقدار بولی دارد که اگر x یک برگ باشد این مقدار True است.
اگر n مرتبه درخت باشد، هر گره داخلی می‌تواند حداکثر دارای n - 1 کلید به همراه یک اشاره گراشاره گر چیست — اشاره گرها در برنامه نویسیاین صفحه عالی توضیح داده اشاره گر چیست و نحوه تعریف اشاره گرها و همین طور اشاره گرها در برنامه نویسی را بررسی کرده سپس انواع اشاره گرها و کاربرد اشاره گرها را گفته به هر فرزند باشد.
هر گره به جز ریشه می‌تواند حداکثر n فرزند و حداقل n/2 فرزند داشته باشد.
همه برگها عمق یکسانی دارند (یعنی ارتفاع درخت).
ریشه حداقل دو فرزند دارد و دارای حداقل 1 کلید است.
اگر n ≥ 1، آنگاه برای هر درخت B از مرتبه n، با ارتفاع h و حداقل درجه t ≥ 2، h ≥ logt (n+1)/2.

حتما بخوانید :

پیمایش درخت، آموزش پیمایش درخت دودویی

عملیات‌های درخت B

در ادامه عملیات‌های جستجو، حذف و درج در درخت B را بررسی خواهیم کرد.

عملیات جستجو در درخت B

جستجو در درختان B شبیه به جستجوی درخت جستجوی باینری است؛ به عنوان مثال، اگر عنصر 49 را در B Tree زیر جستجو کنیم، روند چیزی شبیه به زیر خواهد بود:

عنصر 49 را با گره ریشه 78 مقایسه کنید. چون 49 < 78 است، به زیر درخت سمت چپ آن بروید.
از آنجایی که 40 < 49 < 56، از زیر درخت 40 به سمت راست عبور کنید.
49 > 45، به سمت راست حرکت کنید. عنصر 49 را با 49 مقایسه کنید.
عنصر مورد نظر پیدا شد، آن را برمی‌گردانیم.

عملیات درج در درخت B

درج در سطح گره برگ انجام می‌شود. برای درج یک آیتم در B Tree باید الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد زیر را دنبال کنید:

درخت B را پیمایش کنید تا گره برگ مناسب برای درج گره را بیابید.
اگر گره برگ کمتر از m - 1 کلید دارد، عنصر را به ترتیب افزایشی درج کنید.
در غیر این صورت، اگر گره برگ حاوی m - 1 کلید است، مراحل زیر را دنبال کنید.
عنصر جدید را به ترتیب افزایشی عناصر درج کنید.
گره را از وسط به دو گره تقسیم کنید.
عنصر میانه را به سمت گره والد خود انتقال دهید.
اگر گره والد دارای تعداد m - 1 کلید است، آن را با دنبال کردن مراحل مشابه تقسیم کنید.

برای مثال فرض کنید می‌خواهید عنصر 8 را در درخت B با مرتبه 5 زیر درج کنید:

8 در سمت راست 5 درج می شود، بنابراین 8 را درج کنید.

گره جدید، اکنون حاوی 5 کلید است که بزرگتر از حد مجاز است (5 - 1 = 4) است بنابراین گره را از عنصر میانی یعنی 8 جدا کنید و آن را به سمت گره والد خود که به شکل زیر نشان داده شده است، منتقل کنید:

درخت B نهایی به همین شکل خواهد بود.

حتما بخوانید :

درخت تصمیم یا درخت تصمیم گیری چیست و چگونه کار می کند؟

عملیات حذف از درخت B

حذف نیز در گره‌های برگ انجام می‌شود. گره‌ای که باید حذف شود می‌تواند یک گره برگ یا یک گره داخلی باشد. برای حذف یک گره از درخت B، الگوریتم زیر باید دنبال شود:

محل گره برگ را پیدا کنید.
اگر بیش از m/2 کلید در گره برگ وجود دارد، کلید مورد نظر را از گره حذف کنید.
اگر گره برگ کمتر از m/2 کلید دارد ، با گرفتن عنصر از سمت راست یا چپ، کلیدها را تکمیل کنید.
- اگر گره سمت چپ حاوی بیش از m/2 عناصر است، بزرگترین عنصر آن را به سمت والدش منتقل کنید و عنصر وسط را به سمت پایین به سمت گره‌ای که کلیدش حذف شده است، ببرید.
- اگر گره سمت راست حاوی بیش از m/2 عناصر است، کوچکترین عنصر آن را به سمت والد منتقل کنید و عنصر وسط را به سمت پایین به سمت گره‌ای که کلیدش حذف شده است ببرید.
اگر هیچ یک از گره‌های کناری بیش از m/2 عنصر ندارند، با پیوند دادن دو گره برگ و عنصر میانی گره والد، یک گره برگ جدید ایجاد کنید.
اگر گره‌های والد کمتر از m/2 است، فرآیند بالا را برای والد نیز اعمال کنید.

اگر گره‌ای که باید حذف شود، یک گره داخلی است، آن را با گره قبلی یا بعدی اش در پیمایش Inorder، جایگزین کنید. از آنجایی که گره قبلی یا بعدی همیشه در گره برگ خواهد بود، فرآیند مشابه با حذف گره از گره برگ خواهد بود.

برای مثال فرض کنید می‌خواهید گره 10 را از درخت B مرتبه 5 که در شکل زیر نشان داده شده است حذف کنید:

10 در فرزند سمت راست عنصر 8 وجود دارد، آن را حذف کنید.

در حال حاضر، 23 تنها عنصر باقی مانده در گره است، و از حداقل تعداد عناصری که باید در درخت B درجه 5 وجود داشته باشد، یعنی 2 کمتر است. عناصر موجود در زیردرخت چپ و راست آن نیز کافی نیستند بنابراین آن را با گره‌های چپ و راست و عنصر میانی والد، یعنی 8 ادغام کنید.

درخت B نهایی به صورت زیر است:

پیچیدگی زمانی عملیات‌های درخت B

پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده درخت B برای عملیات‌های جستجو، درج و حذف از مرتبه Θ(log n) است.

پیاده‌سازی درخت B

Python

# Searching a key on a B-tree in Python

# Create a node
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []

# Tree
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

        # Insert node

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

        # Insert nonfull

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k[0] < x.keys[i][0]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k[0] < x.keys[i][0]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k[0] > x.keys[i][0]:
                    i += 1
            self.insert_non_full(x.child[i], k)

        # Split the child

    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(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]

    # 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 in the tree
    def search_key(self, k, x=None):
        if x is not None:
            i = 0
            while i < len(x.keys) and k > x.keys[i][0]:
                i += 1
            if i < len(x.keys) and k == x.keys[i][0]:
                return (x, i)
            elif x.leaf:
                return None
            else:
                return self.search_key(k, x.child[i])

        else:
            return self.search_key(k, self.root)

def main():
    B = BTree(3)

    for i in range(10):
        B.insert((i, 2 * i))

    B.print_tree(B.root)

    if B.search_key(8) is not None:
        print("\nFound")
    else:
        print("\nNot Found")

if __name__ == "__main__":
    main()

# Searching a key on a B-tree in Python

# Create a node
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []

# Tree
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

        # Insert node

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

        # Insert nonfull

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k[0] < x.keys[i][0]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k[0] < x.keys[i][0]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k[0] > x.keys[i][0]:
                    i += 1
            self.insert_non_full(x.child[i], k)

        # Split the child

    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(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]

    # 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 in the tree
    def search_key(self, k, x=None):
        if x is not None:
            i = 0
            while i < len(x.keys) and k > x.keys[i][0]:
                i += 1
            if i < len(x.keys) and k == x.keys[i][0]:
                return (x, i)
            elif x.leaf:
                return None
            else:
                return self.search_key(k, x.child[i])

        else:
            return self.search_key(k, self.root)

def main():
    B = BTree(3)

    for i in range(10):
        B.insert((i, 2 * i))

    B.print_tree(B.root)

    if B.search_key(8) is not None:
        print("\nFound")
    else:
        print("\nNot Found")

if __name__ == "__main__":
    main()

C++

// Searching a key on a B-tree in C++

#include <iostream>
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  n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout  " "  keys[i];
    }

    if (leaf == false)
        C[i]->traverse();
}

TreeNode *TreeNode::search(int k)
{
    int i = 0;
    while (i  n && k > keys[i])
        i++;

    if (keys[i] == k)
        return this;

    if (leaf == true)
        return NULL;

    return C[i]->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]  k)
                i++;
            s->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]  k)
                i++;
        }
        C[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  t - 1; j++)
        z->keys[j] = y->keys[j + t];

    if (y->leaf == false)
    {
        for (int j = 0; j  t; j++)
            z->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\n";
}

// Searching a key on a B-tree in C++

#include <iostream>
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  n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout  " "  keys[i];
    }

    if (leaf == false)
        C[i]->traverse();
}

TreeNode *TreeNode::search(int k)
{
    int i = 0;
    while (i  n && k > keys[i])
        i++;

    if (keys[i] == k)
        return this;

    if (leaf == true)
        return NULL;

    return C[i]->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]  k)
                i++;
            s->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]  k)
                i++;
        }
        C[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  t - 1; j++)
        z->keys[j] = y->keys[j + t];

    if (y->leaf == false)
    {
        for (int j = 0; j  t; j++)
            z->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\n";
}

مقایسه با درخت B+

برجسته‌ترین نقاط مقایسه بین B-tree و B+tree شامل موارد زیر است:

اشاره گر: تمام گره‌های داخلی و برگ در درخت B دارای اشاره‌گر داده هستند. در B+tree، فقط گره‌های برگ دارای اشاره‌گر داده هستند.
جستجو: در B-tree از آنجایی که همه کلیدها در برگ موجود نیستند، جستجو اغلب زمان بیشتری می‌برد. در B+tree، همه کلیدها در گره‌های برگ قرار دارند. از این رو جستجو سریع‌تر و دقیق‌تر است.
کلیدهای تکراری: در درخت B، هیچ کلید تکراری در درخت نگهداری نمی‌شود. در B+tree، کلیدهای تکراری می‌توانند نگه داشته شوند و همه گره‌ها در برگ قرار دارند.
درج: در B-tree ، درج زمان بیشتری می‌برد و گاهی اوقات قابل پیش‌بینی نیست. در B+tree، درج سریع‌تر است و نتایج همیشه یکسان است.
حذف: در درخت B، حذف گره داخلی بسیار پیچیده است و درخت باید دستخوش تغییرات زیادی شود. در B+tree، حذف هر گره آسان است زیرا همه گره‌ها در برگ پیدا می‌شوند.
گره های برگ: گره‌های برگ به صورت ساختمان داده لیست پیوندی در درخت B ذخیره نمی‌شوند. در B+tree، گره های برگ به صورت لیست پیوندیلیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقویلیست پیوندی چیست؟ این صفحه عالی به آموزش لیست پیوندی ساده، دو طرفه و حلقوی با مثال پرداخته و پیاده سازی و عملیات مهم و کاربردهای لیست پیوندی را گفته است ذخیره می‌شوند.
دسترسی: در درخت B، دسترسی متوالی به گر‌ها غیرممکن است. در B+tree، دسترسی متوالی، درست مانند یک لیست پیوندی، امکان‌پذیر است.
ارتفاع: ارتفاع در B-tree برای تعداد خاصی از گره‌ها بزرگتر است. ارتفاع B+tree برای همان تعداد گره از درخت B کمتر است.
کاربرد: B-Trees در پایگاه دادهپایگاه داده چیست؟ – انواع، مفاهیم و کاربردهاپایگاه داده چیست؟ این مقاله به بررسی این موضوع و همچنین انواع پایگاه داده، کاربردهای پایگاه داده، محبوب ترین پایگاه های داده و اجزای اصلی پایگاه داده پرداخته و موتورهای جستجو استفاده می‌شود. درختان B+ در شاخص‌سازی چندسطحی در پایگاه داده استفاده می‌شوند.
تعداد گره ها: در درخت B تعداد گره‌ها در هر سطح میانی l، برابر 2l است. در B+tree، هر گره واسطه می‌تواند n/2 تا n فرزند داشته باشد.

کاربردهای درخت B

از کاربردهای درخت B می‌توان به موارد زیر اشاره کرد:

پایگاه های داده و سیستم‌های مدیریت فایل
برای ذخیره بلوک‌های داده (رسانه‌های ذخیره‌سازی ثانویه)
شاخص‌سازی چندسطحی

جمع‌بندی

B-tree یک درخت جستجوی خود متعادل کننده است که در آن هر گره می‌تواند بیش از یک کلید داشته باشد و بیش از دو فرزند داشته باشد. این درخت، یک شکل تعمیم یافته از درخت جستجوی دودویی است. در این مقاله به شرح این نوع درخت پرداختیم و همچنین عملیات‌های اساسی آن را بررسی کردیم و با کاربردها و پیاده‌سازی آن آشنا شدیم.

درخت B چیست؟

درخت B داده‌ها را به گونه‌ای ذخیره می‌کند که هر گره حاوی کلیدها به ترتیب صعودی باشد. هر یک از این کلیدها دو مرجع به دو گره فرزند دیگر دارند. کلیدهای گره فرزند سمت چپ کمتر از کلید فعلی هستند و کلیدهای گره فرزند سمت راست بیشتر از کلید فعلی هستند.

مزیت اصلی استفاده از B-Trees چیست؟

مزیت استفاده از این نوع درخت شامل موارد زیر است:
کلیدها را به ترتیب مرتب شده برای پیمایش متوالی نگه می‌دارد.
از یک شاخص سلسله مراتبی برای به حداقل رساندن تعداد خواندن دیسک استفاده می‌کند.
از بلوک‌های نیمه کامل برای سرعت بخشیدن به درج و حذف استفاده می‌کند.
شاخص را با یک الگوریتم بازگشتی متعادل نگه می‌دارد.

پیچیدگی زمانی B-tree چقدر است؟

اگر n را تعداد کل عناصر یک درخت B در نظر بگیریم، پیچیدگی زمانی برای هر عملیات رایج، یعنی جستجو، درج و حذف، O(log n) خواهد بود.

درخت B بهتر است یا درخت B+؟

در B-tree، جستجو ناکارآمد است زیرا رکوردها در برگ یا گره‌های داخلی ذخیره می‌شوند. در درخت B+، جستجو بسیار کارآمد یا سریعتر است زیرا تمام رکوردها در گره‌های برگ ذخیره می‌شوند.

مزیت B-tree نسبت به درخت AVL چیست؟

AVL خود متعادل کننده است و تضمین می‌کند که همه عملیات‌ها در حالت متوسط و بدترین حالت O(log n) هستند. علاوه بر این، B-tree با اطمینان از پر بودن گره های داخلی حداقل ضایعات را به حداقل می‌رساند. یک B-tree می‌تواند تعداد دلخواه درج و حذف را مدیریت کند.