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

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

محتویات اعضا

همان‌طور که بیان شد هر عضو دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید های${\displaystyle a_{1}<a_{2}<a_{3}<...<a_{n}}$ باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با ${\displaystyle a_{1}}$ و فرزند دوم آن مقدار کمتر مساوی با ${\displaystyle a_{2}}$ و بیشتر از ${\displaystyle a_{1}}$ دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از ${\displaystyle a_{i-1}}$ و کمتر مساوی با ${\displaystyle a_{i}}$ دارد. تا این جا شبیه داده ساختار درخت است. در بالا بیان شد که هر عضو دارای یک حافظه است و می‌تواند اطلاعت را در ان ذخیره کند. حجم این حافظه نهان هنگام هنگام ساختن درخت مشخص می‌شود.

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

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 {\sqrt {B}}}$ باشد. فرض کنید N عضو در درخت ذخیره کرده‌ایم در این صورت چون هر عضو دارای حافظه به اندازه ${\displaystyle {\sqrt {B}}}$ مقدار است و همچنین درخت متوازن است در نتیجه ارتفاع فرکتال ${\displaystyle log({\frac {N}{\sqrt {B}}})}$ است. توجه کنید log باید در مبنای ${\displaystyle {\sqrt {B}}}$ گرفته شود زیرا هر راس ${\displaystyle {\sqrt {B}}}$ فرزند دارد و در نتیجه ارتفاع درخت${\displaystyle log_{\sqrt {B}}({\frac {N}{\sqrt {B}}})}$ ا. در نتیجه هزینه درج یک عضو${\displaystyle log_{\sqrt {B}}({\frac {N}{\sqrt {B}}})}$ که همان ${\displaystyle log_{\sqrt {B}}(N)}$ است. توجه کنید زمان درج در یک درخت که هر عضو B فرزند دارد برابر با ${\displaystyle log_{B}(N)}$ است و در نتیجه هزینه درج در فرکتال کمتر از هزینه درج در درخت است (زمان درج در فرکتال تقریباً نصف زمان درج در درخت است).

زمان جستجو در یک فرکتال همانند درخت است. در هر مرحله باید لیست مقادیر راسی که در آن هستیم را چک کنیم که این ${\displaystyle O({\sqrt {B}})}$ است و اگر عنصر یافت شد که کار تمام شده و در غیر اینصورت دنبال زیر درخت مناسب می‌رویم. پیدا کردن زیر درخت مناسب از مرتبه ${\displaystyle O({\sqrt {B}})}$ است و چون عمق درخت ${\displaystyle log_{\sqrt {B}}({\frac {N}{\sqrt {B}}})}$ است در نتیجه مدت زمان جستجو برابر است با ${\displaystyle O({\sqrt {B}}log(N))}$ است.

اما مدت زمان جسجو در درخت ${\displaystyle log_{B}(N)}$ است که از اول واضح بود هزینه جستجو در درخت باید کمتر از فرکتال باشد زیرا در فرکتال اعضا دارای حافظه نهان بودند که هزینه جستجو در آن زیاد است.

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

مقایسه فرکتال با درخت

در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای ${\displaystyle {\sqrt {B}}}$ فرزند و ${\displaystyle {\sqrt {B}}}$ مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس ${\displaystyle {\sqrt {B}}}$ است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای ${\displaystyle {\frac {N}{\sqrt {B}}}}$ راس است. در نتیجه حافظه مورد نیاز درخت 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/