هی هابر! ترجمه مقاله را مورد توجه شما قرار می دهم
"چگونه یک پایگاه داده رابطه ای کار می کند".

وقتی صحبت از پایگاه‌های اطلاعاتی رابطه‌ای می‌شود، نمی‌توانم فکر نکنم چیزی گم شده است. آنها در همه جا استفاده می شوند. پایگاه داده های مختلف زیادی وجود دارد، از SQLite کوچک و مفید گرفته تا Teradata قدرتمند. اما تنها چند مقاله وجود دارد که نحوه عملکرد پایگاه داده را توضیح می دهد. می‌توانید با استفاده از «howdoesarelationaldatabasework» خودتان را جستجو کنید تا ببینید چقدر نتایج کم است. علاوه بر این، این مقالات کوتاه هستند. اگر به دنبال جدیدترین فناوری‌های پر سر و صدا (BigData، NoSQL یا JavaScript) هستید، مقاله‌های عمیق‌تری را خواهید دید که نحوه عملکرد آنها را توضیح می‌دهند.

آیا پایگاه‌های اطلاعاتی رابطه‌ای خیلی قدیمی و خسته‌کننده هستند که خارج از دوره‌های دانشگاهی، مقالات تحقیقاتی و کتاب‌ها توضیح داده شوند؟

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

اگرچه عنوان این مقاله صریح است، هدف این مقاله درک نحوه استفاده از پایگاه داده نیست. در نتیجه، از قبل باید بدانید که چگونه یک درخواست اتصال ساده و پرس و جوهای اولیه بنویسید چیز چندش و کثیف; در غیر این صورت ممکن است این مقاله را متوجه نشوید. این تنها چیزی است که باید بدانید، بقیه را توضیح می دهم.

من با برخی از مبانی علوم کامپیوتر، مانند پیچیدگی زمانی الگوریتم ها (BigO) شروع می کنم. می دانم که برخی از شما از این مفهوم متنفر هستید، اما بدون آن نمی توانید پیچیدگی های داخل پایگاه داده را درک کنید. از آنجایی که این یک موضوع بزرگ است، تمرکز خواهم کرد آنچه فکر می کنم مهم است: نحوه پردازش پایگاه داده SQL استعلام. فقط معرفی میکنم مفاهیم پایه پایگاه دادهبه طوری که در پایان مقاله ایده ای از آنچه در زیر کاپوت می گذرد داشته باشید.

از آنجایی که این مقاله طولانی و فنی است که شامل الگوریتم ها و ساختارهای داده زیادی است، وقت خود را صرف مطالعه آن کنید. درک برخی از مفاهیم ممکن است دشوار باشد. می توانید آنها را نادیده بگیرید و همچنان ایده کلی را دریافت کنید.

برای آگاهی بیشتر شما، این مقاله به 3 قسمت تقسیم شده است:

مروری بر اجزای پایگاه داده سطح پایین و سطح بالا
مروری بر فرآیند بهینه سازی پرس و جو
مروری بر معاملات و مدیریت استخر بافر

بازگشت به اصول اولیه

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

در این بخش، برخی از این مفاهیم را به شما یادآوری می کنم زیرا برای درک پایگاه داده ضروری هستند. من همچنین مفهوم را معرفی می کنم فهرست پایگاه داده.

O(1) در مقابل O(n2)

امروزه بسیاری از توسعه دهندگان به پیچیدگی زمانی الگوریتم ها اهمیت نمی دهند... و حق با آنهاست!

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

مفهوم

پیچیدگی زمانی الگوریتم برای مشاهده اینکه یک الگوریتم برای مقدار معینی از داده چقدر طول می کشد تا تکمیل شود. برای توصیف این پیچیدگی، از نماد ریاضی O بزرگ استفاده می‌کنیم. این نماد با تابعی استفاده می‌شود که توضیح می‌دهد یک الگوریتم برای تعداد معینی از ورودی‌ها به چند عملیات نیاز دارد.

برای مثال، وقتی می‌گویم "این الگوریتم پیچیدگی O(some_function()) دارد، به این معنی است که الگوریتم برای پردازش مقدار معینی از داده‌ها، به عملیات some_function (a_certain_amount_of_data) نیاز دارد.

در این مورد، مقدار داده مهم نیست**، در غیر این صورت ** چگونه تعداد عملیات با افزایش حجم داده افزایش می یابد. پیچیدگی زمانی تعداد دقیق عملیات را ارائه نمی دهد، اما روش خوبی برای تخمین زمان اجرا است.

در این نمودار می توانید تعداد عملیات در مقابل مقدار داده های ورودی را برای انواع مختلف پیچیدگی های زمانی الگوریتم مشاهده کنید. من از یک مقیاس لگاریتمی برای نمایش آنها استفاده کردم. به عبارت دیگر، مقدار داده به سرعت از 1 به 1 میلیارد افزایش می یابد.

O(1) یا پیچیدگی ثابت ثابت می ماند (در غیر این صورت پیچیدگی ثابت نامیده نمی شود).
O(ورود به سیستم(n)) حتی با وجود میلیاردها داده پایین می ماند.
بدترین سختی - O(n2)، که در آن تعداد عملیات به سرعت در حال افزایش است.
دو عارضه دیگر به همان سرعت افزایش می یابد.

نمونه

با مقدار کمی داده، تفاوت بین O(1) و O(n2) ناچیز است. برای مثال، فرض کنید شما یک الگوریتم دارید که باید 2000 عنصر را پردازش کند.

الگوریتم O(1) برای شما 1 عملیات هزینه خواهد داشت
الگوریتم O(log(n)) 7 عملیات برای شما هزینه خواهد داشت
الگوریتم O(n) 2 عملیات برای شما هزینه خواهد داشت
الگوریتم O(n*log(n)) 14 عملیات برای شما هزینه خواهد داشت
الگوریتم O(n2) 4 عملیات برای شما هزینه خواهد داشت

تفاوت بین O(1) و O(n2) بزرگ به نظر می رسد (4 میلیون عمل) اما شما حداکثر 2 میلی ثانیه از دست خواهید داد، فقط زمان پلک زدن چشمانتان است. در واقع، پردازنده های مدرن می توانند پردازش کنند صدها میلیون عملیات در ثانیه. به همین دلیل است که عملکرد و بهینه‌سازی در بسیاری از پروژه‌های فناوری اطلاعات موضوعی نیست.

همانطور که گفتم، دانستن این مفهوم هنگام کار با حجم عظیمی از داده ها هنوز مهم است. اگر این بار الگوریتم باید 1 عنصر را پردازش کند (که برای یک پایگاه داده زیاد نیست):

الگوریتم O(1) برای شما 1 عملیات هزینه خواهد داشت
الگوریتم O(log(n)) 14 عملیات برای شما هزینه خواهد داشت
الگوریتم O(n) 1 عملیات برای شما هزینه خواهد داشت
الگوریتم O(n*log(n)) 14 عملیات برای شما هزینه خواهد داشت.
الگوریتم O(n2) 1 عملیات برای شما هزینه خواهد داشت.

من ریاضی را انجام نداده ام، اما می توانم بگویم که با الگوریتم O(n2) زمان برای نوشیدن یک قهوه (حتی دو تا!) دارید. اگر 0 دیگر به حجم داده ها اضافه کنید، وقت خواهید داشت که چرت بزنید.

بیایید عمیق تر برویم

برای اطلاعات شما:

یک جستجوی جدول هش خوب یک عنصر را در O(1) پیدا می کند.
جستجوی یک درخت متعادل نتایجی را در O(log(n)) ایجاد می کند.
جستجوی یک آرایه نتایجی را در O(n) تولید می کند.
بهترین الگوریتم های مرتب سازی دارای پیچیدگی O(n*log(n)) هستند.
یک الگوریتم مرتب سازی بد دارای پیچیدگی O(n2) است.

نکته: در قسمت های بعدی این الگوریتم ها و ساختارهای داده را مشاهده خواهیم کرد.

انواع مختلفی از پیچیدگی زمانی الگوریتم وجود دارد:

سناریوی مورد متوسط
بهترین سناریو
و بدترین سناریو

پیچیدگی زمانی اغلب بدترین سناریو است.

من فقط در مورد پیچیدگی زمانی الگوریتم صحبت کردم، اما پیچیدگی در موارد زیر نیز صدق می کند:

مصرف حافظه الگوریتم
الگوریتم مصرف ورودی/خروجی دیسک

البته عوارض بدتر از n2 وجود دارد، به عنوان مثال:

n4: این وحشتناک است! برخی از الگوریتم های ذکر شده این پیچیدگی را دارند.
3n: این حتی بدتر است! یکی از الگوریتم هایی که در اواسط این مقاله خواهیم دید، این پیچیدگی را دارد (و در واقع در بسیاری از پایگاه های داده استفاده می شود).
فاکتوریل n: شما هرگز نتایج خود را حتی با مقدار کمی داده به دست نخواهید آورد.
nn: اگر با این پیچیدگی مواجه شدید، باید از خود بپرسید که آیا واقعاً این حوزه فعالیت شماست...

توجه: من تعریف واقعی O بزرگ را به شما ارائه نکردم، فقط یک ایده. می توانید این مقاله را در ویکی پدیا برای تعریف واقعی ( مجانبی )

MergeSort

وقتی نیاز به مرتب سازی مجموعه ای دارید چه می کنید؟ چی؟ شما تابع sort() را فرا می خوانید... خوب، پاسخ خوبی است... اما برای یک پایگاه داده، باید بدانید که این تابع sort() چگونه کار می کند.

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

ادغام

مانند بسیاری از الگوریتم‌های مفید، مرتب‌سازی ادغام‌شده به یک ترفند متکی است: ترکیب 2 آرایه مرتب‌شده با اندازه N/2 در یک آرایه مرتب‌شده با عنصر N فقط هزینه N عملیات دارد. این عملیات ادغام نامیده می شود.

بیایید با یک مثال ساده ببینیم این به چه معناست:

این شکل نشان می دهد که برای ساختن آرایه 8 عنصری مرتب شده نهایی، فقط باید یک بار روی 2 آرایه 4 عنصری تکرار کنید. از آنجایی که هر دو آرایه 4 عنصری قبلا مرتب شده اند:

1) شما هر دو عنصر فعلی را در دو آرایه مقایسه می کنید (در ابتدا جریان = اول)
2) سپس کوچکترین را بردارید تا آن را در یک آرایه 8 عنصری قرار دهید
3) و به عنصر بعدی در آرایه بروید که در آن کوچکترین عنصر را گرفته اید
و 1,2,3،XNUMX،XNUMX را تکرار کنید تا به آخرین عنصر یکی از آرایه ها برسید.
سپس عناصر باقی مانده از آرایه دیگر را می گیرید تا آنها را در یک آرایه 8 عنصری قرار دهید.

این کار به این دلیل کار می کند که هر دو آرایه 4 عنصری مرتب شده اند و بنابراین لازم نیست در آن آرایه ها "به عقب" بروید.

اکنون که ترفند را فهمیدیم، در اینجا کد شبه من برای ادغام آمده است:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

مرتب سازی ادغام یک مسئله را به مسائل کوچکتر تقسیم می کند و سپس نتایج مسائل کوچکتر را برای به دست آوردن نتیجه مسئله اصلی پیدا می کند (توجه: به این نوع الگوریتم تقسیم و غلبه می گویند). اگر این الگوریتم را درک نمی کنید، نگران نباشید. اولین بار که دیدمش نفهمیدم اگر می تواند به شما کمک کند، من این الگوریتم را به عنوان یک الگوریتم دو فازی می بینم:

مرحله تقسیم، که در آن آرایه به آرایه های کوچکتر تقسیم می شود
مرحله مرتب‌سازی جایی است که آرایه‌های کوچک با هم ترکیب می‌شوند (با استفاده از اتحاد) تا یک آرایه بزرگ‌تر را تشکیل دهند.

مرحله تقسیم

در مرحله تقسیم آرایه در 3 مرحله به آرایه های واحد تقسیم می شود. تعداد رسمی مراحل log(N) است (از آنجایی که N=8، log(N) = 3).

این را از کجا می دانم؟

من نابغه هستم! در یک کلام - ریاضیات. ایده این است که هر مرحله اندازه آرایه اصلی را بر 2 تقسیم می کند. تعداد مراحل تعداد دفعاتی است که می توانید آرایه اصلی را به دو تقسیم کنید. این تعریف دقیق لگاریتم است (مبنای 2).

مرحله مرتب سازی

در مرحله مرتب سازی، شما با آرایه های واحد (تک عنصری) شروع می کنید. در طول هر مرحله چندین عملیات ادغام را اعمال می کنید و هزینه کل N = 8 عملیات است:

در مرحله اول شما 4 ادغام دارید که هر کدام 2 عملیات هزینه دارد
در مرحله دوم شما 2 ادغام دارید که هر کدام 4 عملیات هزینه دارد
در مرحله سوم 1 ادغام دارید که 8 عملیات هزینه دارد

از آنجایی که مراحل log(N) وجود دارد، هزینه کل N * عملیات log(N).

مزایای مرتب سازی ادغام

چرا این الگوریتم اینقدر قدرتمند است؟

زیرا:

می‌توانید آن را برای کاهش ردپای حافظه تغییر دهید تا آرایه‌های جدید ایجاد نکنید، بلکه مستقیماً آرایه ورودی را تغییر دهید.

نکته: این نوع الگوریتم نامیده می شود in-محل (مرتب سازی بدون حافظه اضافی).

می‌توانید آن را به گونه‌ای تغییر دهید که از فضای دیسک و مقدار کمی حافظه به طور همزمان استفاده کند بدون اینکه هزینه ورودی/خروجی قابل توجهی روی دیسک وارد شود. ایده این است که فقط آن بخش هایی را در حافظه بارگذاری کنیم که در حال حاضر در حال پردازش هستند. این مهم زمانی است که شما نیاز به مرتب سازی یک جدول چند گیگابایتی تنها با یک بافر حافظه 100 مگابایتی دارید.

نکته: این نوع الگوریتم نامیده می شود مرتب سازی خارجی.

می‌توانید آن را طوری تغییر دهید که روی چندین فرآیند/رشته/سرور اجرا شود.

به عنوان مثال، مرتب سازی ادغام توزیع شده یکی از اجزای کلیدی است هادوپ (که یک ساختار در داده های بزرگ است).

این الگوریتم می تواند سرب را به طلا تبدیل کند (واقعاً!).

این الگوریتم مرتب‌سازی در اکثر پایگاه‌های داده (اگر نه همه) استفاده می‌شود، اما تنها الگوریتم نیست. اگر می خواهید بیشتر بدانید، می توانید این مطلب را بخوانید کار پژوهشی، که مزایا و معایب الگوریتم های مرتب سازی پایگاه داده رایج را مورد بحث قرار می دهد.

آرایه، درخت و جدول هش

اکنون که ایده پیچیدگی زمانی و مرتب‌سازی را فهمیدیم، باید در مورد 3 ساختار داده به شما بگویم. این مهم است زیرا آنها اساس پایگاه های داده مدرن هستند. من همچنین مفهوم را معرفی می کنم فهرست پایگاه داده.

آرایه

یک آرایه دو بعدی ساده ترین ساختار داده است. جدول را می توان به عنوان یک آرایه در نظر گرفت. مثلا:

این آرایه دو بعدی یک جدول با سطر و ستون است:

هر خط نشان دهنده یک موجودیت است
ستون ها ویژگی هایی را که موجودیت را توصیف می کنند ذخیره می کنند.
هر ستون داده های یک نوع خاص (عدد صحیح، رشته، تاریخ...) را ذخیره می کند.

این برای ذخیره و تجسم داده ها راحت است، با این حال، زمانی که شما نیاز به پیدا کردن یک مقدار خاص دارید، این مناسب نیست.

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

توجه: بیشتر پایگاه‌های داده مدرن، آرایه‌های گسترده‌ای را برای ذخیره‌سازی کارآمد جداول ارائه می‌کنند: جداول سازمان‌دهی شده توسط heap و جداول سازمان‌دهی شده با فهرست. اما این مشکل پیدا کردن سریع یک شرایط خاص در یک گروه از ستون‌ها را تغییر نمی‌دهد.

درخت و فهرست پایگاه داده

درخت جستجوی دودویی یک درخت باینری با ویژگی خاص است، کلید هر گره باید این باشد:

بزرگتر از تمام کلیدهای ذخیره شده در زیردرخت سمت چپ
کمتر از همه کلیدهای ذخیره شده در زیردرخت سمت راست

بیایید ببینیم این به چه معناست

فکر

این درخت N = 15 عنصر دارد. فرض کنید من به دنبال 208 هستم:

من از ریشه شروع می کنم که کلید آن 136 است. از 136<208، به زیر درخت سمت راست گره 136 نگاه می کنم.
398>208 بنابراین من به زیر درخت سمت چپ گره 398 نگاه می کنم
250>208 بنابراین من به زیر درخت سمت چپ گره 250 نگاه می کنم
200<208، بنابراین من به زیردرخت سمت راست گره 200 نگاه می کنم. اما 200 زیردرخت سمت راست ندارد، ارزش وجود ندارد (چون اگر وجود داشته باشد در زیر درخت سمت راست 200 قرار می گیرد).

حالا فرض کنید من دنبال 40 هستم

من از ریشه شروع می کنم که کلید آن 136 است. از 136 > 40، به زیردرخت سمت چپ گره 136 نگاه می کنم.
80 > 40، از این رو من به زیردرخت سمت چپ گره 80 نگاه می کنم
40 = 40، گره وجود دارد. شناسه ردیف داخل گره را بازیابی می کنم (در تصویر نشان داده نشده است) و شناسه ردیف داده شده را در جدول جستجو می کنم.
دانستن شناسه ردیف به من امکان می دهد دقیقاً بدانم داده ها در کجای جدول هستند، بنابراین می توانم آن را فوراً بازیابی کنم.

در پایان، هر دو جستجو به تعداد سطوح داخل درخت برای من هزینه خواهد داشت. اگر قسمت مربوط به مرتب سازی ادغام را به دقت بخوانید، باید ببینید که سطوح log(N) وجود دارد. معلوم می شود، گزارش هزینه جستجو (N)، بد نیست!

به مشکل خود برگردیم

اما این بسیار انتزاعی است، بنابراین اجازه دهید به مشکل خود بازگردیم. به جای یک عدد صحیح ساده، رشته ای را تصور کنید که کشور فردی را در جدول قبلی نشان می دهد. فرض کنید درختی دارید که حاوی فیلد "کشور" (ستون 3) جدول است:

اگر می خواهید بدانید چه کسانی در انگلستان کار می کنند
شما به درخت نگاه می کنید تا گره ای را به دست آورید که نشان دهنده بریتانیای کبیر است
در داخل "UKnode" محل سوابق کارگران بریتانیا را خواهید یافت.

اگر مستقیماً از آرایه استفاده کنید، این جستجو هزینه عملیات log(N) را به جای عملیات N خواهد داشت. چیزی که شما ارائه کردید این بود فهرست پایگاه داده.

شما می توانید یک درخت شاخص برای هر گروه از فیلدها (رشته، شماره، 2 خط، شماره و رشته، تاریخ...) بسازید تا زمانی که تابعی برای مقایسه کلیدها (به عنوان مثال گروه های فیلد) داشته باشید تا بتوانید تنظیم کنید. ترتیب در میان کلیدها (که برای هر نوع پایه در پایگاه داده صدق می کند).

B+TreeIndex

در حالی که این درخت برای بدست آوردن یک مقدار خاص به خوبی کار می کند، در صورت نیاز یک مشکل بزرگ وجود دارد چندین عنصر را بین دو مقدار دریافت کنید. این هزینه O(N) خواهد داشت زیرا باید به هر گره در درخت نگاه کنید و بررسی کنید که آیا بین این دو مقدار است (مثلاً با پیمایش منظم درخت). علاوه بر این، این عملیات برای ورودی/خروجی دیسک مناسب نیست زیرا باید کل درخت را بخوانید. ما باید راهی برای اجرای کارآمد پیدا کنیم درخواست محدوده. برای حل این مشکل، پایگاه های داده مدرن از نسخه اصلاح شده درخت قبلی به نام B+Tree استفاده می کنند. در درخت B+Tree:

فقط پایین ترین گره ها (برگ ها) ذخیره اطلاعات (محل ردیف ها در جدول مربوطه)
بقیه گره ها اینجا هستند برای مسیریابی به گره صحیح در طول جستجو.

همانطور که می بینید، گره های بیشتری در اینجا وجود دارد (دوبار). در واقع، شما گره‌های اضافی، "گره‌های تصمیم‌گیری" دارید که به شما کمک می‌کنند گره صحیح را پیدا کنید (که مکان ردیف‌ها را در جدول مرتبط ذخیره می‌کند). اما پیچیدگی جستجو همچنان O(log(N)) است (فقط یک سطح دیگر وجود دارد). تفاوت بزرگ در این است گره های سطح پایین به جانشینان خود متصل می شوند.

با این B+Tree، اگر به دنبال مقادیر بین 40 و 100 هستید:

شما فقط باید به دنبال 40 باشید (یا نزدیکترین مقدار بعد از 40 اگر 40 وجود نداشته باشد) مانند درخت قبلی.
سپس 40 وارث را با استفاده از پیوندهای مستقیم وارث جمع آوری کنید تا به 100 نفر برسید.

فرض کنید M جانشینان را پیدا کردید و درخت N گره دارد. یافتن یک گره خاص مانند درخت قبلی log(N) هزینه دارد. اما هنگامی که این گره را دریافت کردید، جانشین های M را در عملیات M با ارجاع به جانشینان آنها دریافت خواهید کرد. این جستجو فقط هزینه M+log(N) دارد عملیات در مقایسه با عملیات N در درخت قبلی. علاوه بر این، لازم نیست درخت کامل را بخوانید (فقط گره‌های M+log(N)، که به معنای استفاده کمتر از دیسک است. اگر M کوچک باشد (مثلاً 200 ردیف) و N بزرگ (1 ردیف)، تفاوت بزرگی وجود خواهد داشت.

اما مشکلات جدیدی در اینجا وجود دارد (دوباره!). اگر یک ردیف را در پایگاه داده (و بنابراین در شاخص B+Tree مرتبط) اضافه یا حذف کنید:

شما باید نظم را بین گره های داخل یک B+Tree حفظ کنید، در غیر این صورت نمی توانید گره های داخل درخت مرتب نشده را پیدا کنید.
شما باید حداقل تعداد سطوح ممکن را در B+Tree نگه دارید، در غیر این صورت پیچیدگی زمانی O(log(N)) O(N) می شود.

به عبارت دیگر، B+Tree باید خود منظم و متعادل باشد. خوشبختانه این کار با عملیات حذف و درج هوشمند امکان پذیر است. اما این هزینه دارد: درج و حذف در درخت B+ هزینه O(log(N)) دارد. به همین دلیل است که برخی از شما این را شنیده اید استفاده از شاخص های زیاد ایده خوبی نیست. واقعا، شما سرعت درج/به روز رسانی/حذف سریع یک ردیف در جدول را کاهش می دهیدزیرا پایگاه داده باید شاخص های جدول را با استفاده از عملیات گران قیمت O(log(N)) برای هر شاخص به روز کند. علاوه بر این، افزودن ایندکس ها به معنای حجم کار بیشتر است مدیر معاملات (در پایان مقاله توضیح داده خواهد شد).

برای جزئیات بیشتر، می توانید مقاله ویکی پدیا را مشاهده کنید B+درخت. اگر مثالی از پیاده سازی B+Tree در پایگاه داده می خواهید، نگاهی بیندازید این مقاله и این مقاله از یک توسعه دهنده پیشرو MySQL. هر دوی آنها بر نحوه مدیریت InnoDB (موتور MySQL) ایندکس ها تمرکز می کنند.

توجه: خواننده ای به من گفت که به دلیل بهینه سازی های سطح پایین، درخت B+ باید کاملاً متعادل باشد.

قابل هشتم شدن

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

جدول هش یک ساختار داده است که به سرعت یک عنصر را توسط کلید خود پیدا می کند. برای ساخت یک جدول هش باید تعریف کنید:

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

مثال ساده

بیایید یک مثال واضح بیاوریم:

این جدول هش دارای 10 بخش است. چون من تنبل هستم، فقط 5 قسمت را تصویر کردم، اما می دانم که شما باهوش هستید، بنابراین به شما اجازه می دهم که 5 قسمت دیگر را خودتان تصویر کنید. من از یک تابع هش مدول 10 کلید استفاده کردم. به عبارت دیگر، من فقط آخرین رقم کلید عنصر را ذخیره می کنم تا بخش آن را پیدا کنم:

اگر آخرین رقم 0 باشد، عنصر در بخش 0 قرار می گیرد،
اگر آخرین رقم 1 باشد، عنصر در بخش 1 قرار می گیرد،
اگر آخرین رقم 2 باشد، عنصر در ناحیه 2 قرار می گیرد،
...

تابع مقایسه ای که من استفاده کردم به سادگی برابری بین دو عدد صحیح است.

فرض کنید می خواهید عنصر 78 را دریافت کنید:

جدول هش کد هش 78 را محاسبه می کند که 8 است.
جدول هش به بخش 8 نگاه می کند و اولین عنصری که پیدا می کند 78 است.
او مورد 78 را به شما برمی گرداند
جستجو فقط 2 عملیات هزینه دارد (یکی برای محاسبه مقدار هش و دیگری برای جستجوی عنصر درون بخش).

حال فرض کنید می خواهید عنصر 59 را دریافت کنید:

جدول هش کد هش 59 را محاسبه می کند که 9 است.
جدول هش در بخش 9 جستجو می کند، اولین عنصر یافت شده 99 است. از آنجایی که 99!=59، عنصر 99 یک عنصر معتبر نیست.
با استفاده از همین منطق، عنصر دوم (9)، سوم (79)، ...، آخرین (29) گرفته شده است.
عنصر پیدا نشد.
جست و جو 7 عملیات هزینه داشت.

عملکرد هش خوب

همانطور که می بینید، بسته به ارزشی که به دنبال آن هستید، هزینه آن یکسان نیست!

اگر اکنون ماژول تابع هش 1،000،000 کلید را تغییر دهم (یعنی گرفتن 6 رقم آخر)، جستجوی دوم فقط 1 عملیات هزینه دارد زیرا هیچ عنصری در بخش 000059 وجود ندارد. چالش واقعی پیدا کردن یک تابع هش خوب است که سطل هایی حاوی تعداد بسیار کمی از عناصر را ایجاد کند.

در مثال من، یافتن یک تابع هش خوب آسان است. اما این یک مثال ساده است، یافتن یک تابع هش خوب زمانی که کلید این است دشوارتر است:

رشته (به عنوان مثال - نام خانوادگی)
2 خط (به عنوان مثال - نام خانوادگی و نام)
2 خط و تاریخ (به عنوان مثال - نام خانوادگی، نام و تاریخ تولد)
...

با یک تابع هش خوب، جستجوی جدول هش هزینه O(1) دارد..

آرایه در مقابل جدول هش

چرا از آرایه استفاده نمی کنید؟

هوم، سوال خوبی است.

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

برای کسب اطلاعات بیشتر می توانید مقاله مربوط به آن را مطالعه کنید جاوهHashMap، که اجرای کارآمد جدول هش است. برای درک مفاهیم مطرح شده در این مقاله، نیازی به درک جاوا ندارید.

منبع: www.habr.com

نحوه عملکرد پایگاه های داده رابطه ای (قسمت 1)