شماره گذاری درخت فرکتال
در علوم کامپیوتر، درخت فرکتال یکی از انواع داده ساختارهای درخت است که می‌تواند اطلاعات را ذخیره و نگهداری کند و می‌توان به اطلاعات آن دسترسی داشت یا همچنین اطلاعات مشخصی را در آن جستجو کرد. این داده ساختار شباهت زیادی به درخت دارد. این داده ساختار نیز شبیه درخت تعمیمی از درخت جست جوی دودویی است. در درخت جستجوی دودویی هر عضو دارای حداکثر دو بچه است (اصطلاحاً فرزند چپ و راست) ولی در درخت فرکتال هر عضو می‌تواند تعداد دلخواهی فرزند داشته باشد و معمولاً یک عدد به عنوان حداکثر تعداد فرزندان وجود دارد که هنگام ساختن فرکتال داده می‌شود. در این داده ساختار در هر عضو تعدادی کلید وجود دارد که در هنگام جستجو به کار می‌آید. همچنین در هر عضو از درخت فرکتال، حافظه‌ای وجود دارد که می‌تواند اطلاعات رو ذخیره کند. این حافظه بسیار شبیه به است. درخت فرکتال کاربرد زیادی در دارد و در ادامه خواهیم دید که که این ساختار برای حافظه‌های خارجی بسیار مناسب است.
همان‌طور که بیان شد هر عضو دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید هایformula_1 باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با formula_2 و فرزند دوم آن مقدار کمتر مساوی با formula_3 و بیشتر از formula_2 دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از formula_5 و کمتر مساوی با formula_6 دارد. تا این جا شبیه داده ساختار درخت است. در بالا بیان شد که هر عضو دارای یک حافظه است و می‌تواند اطلاعت را در ان ذخیره کند. حجم این حافظه نهان هنگام هنگام ساختن درخت مشخص می‌شود.
حال در اینجا با استفاده از زبان برنامه‌نویسی پایتون یک کلاس برای اعضا می‌نویسیم. class Node: برای اضافه کردن یک عضو جدید به صورت بازگشتی عمل می‌کنیم. فرض می‌کنیم یک مقدار و یک عضو فرکتال به ما داده شده‌است. اگر حافظه نهان آن عضو دارای ظرفیت خالی بود آن مقدار (شی) را به آن اضافه می‌کنیم. در غیر این صورت زیر درختی که این مقدار باید در آن اضافه شود را پیدا می‌کنیم و تابع درج را به صورت بازگشتی برای آن مقدار (شی) فراخوانی می‌کنیم. در حالتی که ریز درختی که باید مقدار به آن اضافه شود تهی بود، یک برگ جدید ساخته و آن را فرزند عضو فعلی قرار داده و تابع را برای عضو جدید ساخته شده دوباره فراخوانی می‌کنیم. بقیه توابع مانند جستجو، حذف و … شبیه داده ساختار درخت است با این تفاوت که هر عضو خود دارای یک لیست از مقادیر است به جای یک مقدار. def insert(node, value): در اینجا فرض می‌کنیم درخت فرکتال متوازن است. فرض کنید یک راس در فرکتال حداکثر formula_7 عضو داشته باشد. در این صورت فرض می‌کنیم حجم حافظه نهان هم formula_7 باشد. فرض کنید N عضو در درخت ذخیره کرده‌ایم در این صورت چون هر عضو دارای حافظه به اندازه formula_7 مقدار است و همچنین درخت متوازن است در نتیجه ارتفاع فرکتال formula_10 است. توجه کنید log باید در مبنای formula_7 گرفته شود زیرا هر راس formula_7 فرزند دارد و در نتیجه ارتفاع درختformula_13 ا. در نتیجه هزینه درج یک عضوformula_13 که همان formula_15 است. توجه کنید زمان درج در یک درخت که هر عضو B فرزند دارد برابر با formula_16 است و در نتیجه هزینه درج در فرکتال کمتر از هزینه درج در درخت است (زمان درج در فرکتال تقریباً نصف زمان درج در درخت است).
زمان جستجو در یک فرکتال همانند درخت است. در هر مرحله باید لیست مقادیر راسی که در آن هستیم را چک کنیم که این formula_17 است و اگر عنصر یافت شد که کار تمام شده و در غیر اینصورت دنبال زیر درخت مناسب می‌رویم. پیدا کردن زیر درخت مناسب از مرتبه formula_17 است و چون عمق درخت formula_13 است در نتیجه مدت زمان جستجو برابر است با formula_20 است.
اما مدت زمان جسجو در درخت formula_16 است که از اول واضح بود هزینه جستجو در درخت باید کمتر از فرکتال باشد زیرا در فرکتال اعضا دارای حافظه نهان بودند که هزینه جستجو در آن زیاد است.
هزینه حذف کردن هم که برابر با هزینه جستجو است. (در واقع اگر بدانیم مقداری که می‌خواهیم حذف کنیم در کدام راس است هزینه حذف formula_22 است.
در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای formula_7 فرزند و formula_7 مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس formula_7 است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای formula_26 راس است. در نتیجه حافظه مورد نیاز درخت B برابر فرکتال است.
یکی دیگر از مزیت‌های فرکتال زمانی است که از این الگوریتم در حافظه دیسک‌ها استفاده شود. فرض کنید اطلاعات را در دو دیسک ذخیره کرده‌اید که یکی با الگوریتم درخت و دیگری با فرکتال کار می‌کند. در این صورت می‌دانیم هزینه دسترسی و خواندن اطلاعات از دیسک بسیار زیاد است و می‌خواهیم تا جای ممکن دسترسی به دیسک را کاهش دهیم. در این صورت در دیسکی که با الگوریتم درخت کار می‌کند برای خواندن یک مقدار باید ابتدا ان را جستجو کرد و سپس آن را از دیسک خواند و به حافظه نهان آورد. حال برای مقدار بعدی دوباره باید همین کار را انجام داد. اما اگر دیسک با الگوریتم فرکتال کار کند بعد از پیدا کردن مقدار می‌توان کل حافظه نهان راس را به حافظه نهان آورد و طبق اصل محلی دسترسی‌ها، تعداد دسترسی‌ها به حافظه کمتر می‌شود و مخصوصاً زمانی که بخواهیم عمل نوشتن در حافظه انجام دهیم این اختلاف محسوس تر است.