شماره گذاری درخت فرکتال

همان‌طور که بیان شد هر عضو دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید های

حال در اینجا با استفاده از زبان برنامه‌نویسی پایتون یک کلاس برای اعضا می‌نویسیم.

class Node:
    def __init__(self, max_child, max_cache, key):
        self.max_cache = max_cache
        self.cache = []
        self.max_child = max_child
        self.child = []
        self.key = key
    def isfull(self):
        if len(self.cache) == self.max_cache:
            return True
        else:
            return False

برای اضافه کردن یک عضو جدید به صورت بازگشتی عمل می‌کنیم. فرض می‌کنیم یک مقدار و یک عضو فرکتال به ما داده شده‌است. اگر حافظه نهان آن عضو دارای ظرفیت خالی بود آن مقدار (شی) را به آن اضافه می‌کنیم. در غیر این صورت زیر درختی که این مقدار باید در آن اضافه شود را پیدا می‌کنیم و تابع درج را به صورت بازگشتی برای آن مقدار (شی) فراخوانی می‌کنیم. در حالتی که ریز درختی که باید مقدار به آن اضافه شود تهی بود، یک برگ جدید ساخته و آن را فرزند عضو فعلی قرار داده و تابع را برای عضو جدید ساخته شده دوباره فراخوانی می‌کنیم. بقیه توابع مانند جستجو، حذف و … شبیه داده ساختار درخت است با این تفاوت که هر عضو خود دارای یک لیست از مقادیر است به جای یک مقدار.

def insert(node, value):
    if node.isfull == False:
        node.cache += [value]
    else:
        for i in range(len(node.key)):
            if value <= node.key[i]:
                if node.child[i] != None:
                    return insert(node.child[i], value)
                else:
                    new = Node (node.max_child, node.max_cache, node.key)
                    new.cache += [value]
                    node.child[i] = new
                    return insert(new, value)
                return 0

در اینجا فرض می‌کنیم درخت فرکتال متوازن است. فرض کنید یک راس در فرکتال حداکثر ${\displaystyle \sqrt{B}}$

زمان جستجو در یک فرکتال همانند درخت است. در هر مرحله باید لیست مقادیر راسی که در آن هستیم را چک کنیم که این ${\displaystyle O(\sqrt{B})}$

اما مدت زمان جسجو در درخت ${\displaystyle lo{g}_B(N)}$

هزینه حذف کردن هم که برابر با هزینه جستجو است. (در واقع اگر بدانیم مقداری که می‌خواهیم حذف کنیم در کدام راس است هزینه حذف ${\displaystyle O(1)}$

در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای ${\displaystyle \sqrt{B}}$

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

1. فراکتال
2. درخت (ساختار داده)
3. درخت جستجوی دودویی
4. حافظه نهان

1. https://en.wikipedia.org/wiki/Fractal_tree_index
2. https://en.wikipedia.org/wiki/B-tree
3. https://www.percona.com/blog/2013/02/27/mongodb-fractal-tree-indexes-high-compression/