Lecture 15 Indexed Sequential Access, B+trees, Simple prefix B+trees (Sections 10.1 – 10.5)
In the Name of God
File Structure
Indexed Sequential Access B+trees, Simple prefix B+trees
انواع روش های مورد نیازجهت دسترسی به داده های یک فایل کدامند؟
منظوراز روش Indexed Sequential چیست؟
ساختارایندکس ISAM چگونه بوده است؟
آیا ایندکس B-tree امکان دسترسی سری به رکوردها را بترتیب کلید میدهد؟
چگونه دسترسی سری به رکوردهای یک فایل بترتیب کلید میسر میشود؟
ساختار یک Sequence Set چگونه است؟
ساختارایندکس B+tree چگونه است؟
ساختارایندکس Simple Prefix B+tree چگونه است؟
File Structure
Indexed Sequential Access
انواع روش های مورد نیازجهت دسترسی به داده های یک فایل کدامند؟
روش دسترسی بکمک ایندکس (Indexed Access Method )
دسترسی به بعضی ازرکوردهای فایل با استفاده از کلید و ایندکس.
روش دسترسی سری (Sequential Access Method )
دسترسی به کلیه رکوردهای فایل بترتیب کلید اصلی ولی بدون استفاده از ایندکس. (چرا؟)
در اینصورت باید رکوردهای فایل بطور فیزیکی بر حسب کلید اصلی مرتب شده باشند.
کاربرد این روش در بعضی پردازش ها (Batch Processing) که احتیاج به تکرار عملیات روی تمام رکوردهای فایل دارند میباشد.
مثال : پرداخت حقوق ماهیانه کارمندان یک سازمان.
File Structure
History : ISAM File
ساختارایندکس های ISAM چگونه بوده است؟
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
Ex: Reorganization
History : ISAM File
ساختارایندکس های ISAM چگونه بوده است؟
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
Indexed Sequential Access
آیا ایندکس B-tree امکان دسترسی سری به رکوردها را بترتیب کلید میدهد؟
در ایندکس B-tree :
نودهای برگی فقط شامل کلیدها واشاره گرهایی به رکوردهای داده میباشند.
هیچگونه ترتیب خاصی برای رکوردهای داده تعریف نگردیده است.
دسترسی سری به رکوردهای داده بترتیب کلید ممکن نمیباشد. (چرا؟)
چگونه دسترسی سری به رکوردهای یک فایل بترتیب کلید میسر میشود؟
برای اجتناب از لزوم مرتب سازی (sort) کلیه رکورد های یک فایل،
میتوان فایل را به صورت بلوکهایی از رکوردهای مرتب شده نگهداری نمود.
این ساختار موسوم به Sequence Set میباشد.
File Structure
Indexed Sequential Access
ساختار یک Sequence Set چگونه است؟
رکوردهای فایل به تعدادی بلوک گروه بندی میشوند.
هر بلوک حاوی لااقل نصف ظرفیت خود از رکوردها میباشد.
رکوردهای داخل هر بلوک مرتب شده (sorted) میباشد.
بلوک ها نیز در رابطه با یکدیگر مرتب شده میباشند.
ولی ترتیب آنها بطور فیزیکی نیست. بلکه با استفاده ازاشاره گر تامین میشود.
عملیات حذف و اضافه رکوردها شبیه عملیات در گره های B-Tree میباشند.
ایجاد (insertion) یک رکورد در بلوک مخصوص خود (با توجه به کلید آن) ممکن است باعث شکسته شدن (Block Splitting) بشود. (overflow)
حذف (deletion) یک رکورد در یک بلوک ممکن است باعث ادغام دو بلوک Block Merging یا Block Redistribution بشود. (underflow)
File Structure
Sequence Set
مثال:
(شکل 10.1 صفحه 427 کتاب)
File Structure
Sequence Set
مثال (ادامه…):
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
Sequence Set
مثال (ادامه…):
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
Sequence Set
مزایای ساختار sequence set چیست؟
احتیاجی به مرتب سازی کلیه رکوردهای فایل بعد ازهرعمل ایجاد یا حذف رکورد نمیباشد.
معایب ساختار sequence set چیست؟
فضای دیسک بیشتری برای نگهداری فایل لازم است.
چون بلوک ها می توانند %50 ظرفیت خود رکورد داشته باشند.
ترتیب فیزیکی رکوردها فقط در داخل یک بلوک صادق است )نه در کل فایل(.
File Structure
Sequence Set
شرایط انتخاب اندازه هر بلوک چگونه است؟
بسته به روش Merge / Redistribution موردنظر بایستی حافظه RAM فضای لازم برای لااقل 2 یا 3 بلوک را داشته باشد.
بهتر است که برای خواندن هر بلوک فقط یک دسترسی به دیسک (seek) احتیاج باشد.
در دیسک های سکتور بندی شده اندازه هر بلوک میتواند معادل یک cluster انتخاب شود.
در دیسک های بلوک بندی شده اندازه هر بلوک می تواند معادل یک Track ( یا نصف آن ) انتخاب شود.
File Structure
Sequence Set
روش ایجاد ایندکس B-tree با توجه به ساختار Sequence Set چگونه است؟
File Structure
ساختار ایندکس B+Tree
ساختاریک ایندکس B+tree چگونه است؟
ساختار ایندکس B+Tree شبیه به ساختار ایندکس در B-Tree میباشد، ولی با دو تفاوت:
در B+Tree کوچکترین کلید هر نود به عنوان reference در نود parent ظاهر میشود.
2) حضور اولین کلید در نود parent به طور مجازی میباشد.
Key1
مجازی
Key1……….
Key2……….
Key3……….
File Structure
ساختاریک ایندکس Simple Prefix B+tree چگونه است؟
با توجه به ساختار sequence set میتوان با استفاده از separator های کوتاه بین محتوای بلوک ها تمیز قائل شد.
Block No. Range of Keys Separator
1 Adams-Berne
2 Bolen-Cage
3 Camp-Dutton
4 Embry-Evans
5 Faber-Folk
6 Folks-Gaddis
Simple Prefix B+Tree
مثال:
File Structure
مثال: (شکل 10.7 صفحه 434 کتاب)
Simple Prefix B+Tree
ساختاریک ایندکس Simple Prefix B+tree چگونه است؟
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ