CoE KKU

โครงสร้างข้อมูลที่กล่าวถึงมาแล้วนั้นตั้งอยู่บนสมมติฐานที่ว่า โครงสร้างทั้งหมดสามารถจัดเก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ได้ ถ้าจำนวนข้อมูลมีปริมาณมากเกินกว่าที่จะเก็บไว้ในหน่วยความจำหลักของเครื่องได้ทั้งหมด ก็หมายความว่าต้องเก็บมันไว้ในแผ่นจานแม่เหล็ก ซึ่งกรณีเช่นนี้โมเดล Big-O ที่ใช้ในการวิเคราะห์ก็จะไม่มีความหมายอีกต่อไป ทั้งนี้เนื่องจากว่าการเข้าถึงข้อมูลในแผ่นจานแม่เหล็กนั้นใช้ค่าใช้จ่าย (เวลา) ที่แพงมากจนกระทั่ง running time ไม่มีนัยสำคัญใด ๆ อีกต่อไป

พิจารณาข้อเท็จจริงต่อไปนี้ – ถ้าเครื่องคอมพิวเตอร์เป็นเครื่องที่ทำงานด้วยความเร็ว 25 MIPs ก็สามารถกล่าวได้ว่ามันมีขีดความสามรถในการประมวลผลที่เป็นไปได้ คือ 25 ล้านคำสั่งต่อวินาที (instructions/sec) และถ้าเครื่องนี้มีเครื่องขับจานแม่เหล็ก (disk drive) ความเร็ว 3600 RPM (ที่เร็วกว่านี้ก็มี คือ 7500, ถึง 10000 RPMs) นั่นคือ มันสามารถหมุนจานได้ 3600 รอบในหนึ่งนาที หรือก็คือหนึ่งรอบการหมุนใช้เวลา 1/60 วินาที หรือ 16.7 mSec. และถ้าเราคิดว่าโดยเฉลี่ยแล้วต้องใช้การหมุนครึ่งรอบจึงจะได้ข้อมูลที่ต้องการและถ้าเราไม่คำนึงถึงปัจจัยอื่น ๆ เลย ก็หมายความว่าเราต้องใช้เวลา 8.3 mSec.

เพื่อให้ได้ข้อมูลที่ต้องการ ผลก็คือเราสามารถเข้าถึงข้อมูลที่ต้องการได้เป็นจำนวนโดยประมาณ 120 ครั้งต่อวินาที ซึ่งเป็นจำนวนข้อมูลที่จะได้รับไม่น้อยเลย แต่หากนำมันไปเปรียบเทียบกับความสามารถในการทำงาน 25 ล้านคำสั่งใน 1 วินาทีแล้ว ก็ไม่สามารถเทียบกันไม่ได้เลย หรือกล่าวอีกแบบหนึ่งได้ว่า การเข้าถึงจานแม่เหล็กแต่ละครั้งมีค่าเท่ากับการทำงาน 200,000 คำสั่ง นี่แสดงให้เห็นว่าการเข้าถึงแผ่นจานแม่เหล็กเป็นการทำงานที่มีค่าใช้จ่ายสูงมาก ดังนั้นในการประมวลผลที่ต้องเข้าถึงแผ่นจานแม่เหล็กนั้น การลดจำนวนการเข้าถึงแผ่นจานแม่เหล็กลงครึ่งหนึ่งก็หมายความว่าเราลด running time ลงครึ่งหนึ่งเช่นกัน

กล่าวสำหรับการทำงานของ search tree ในแผ่นจานแม่เหล็ก ถ้าให้มีจำนวนข้อมูล 10 ล้านหน่วยข้อมูล โดยแต่ละหน่วยใช้เนื้อที่ 32 ไบต์ และแต่ละระเบียนใช้ 256 ไบต์ และถ้าข้อมูลทั้งหมดไม่สามารถบรรจุลงในหน่วยความจำได้ทั้งหมดในคราวเดียว ถ้าให้เราเป็นผู้ใช้งานระบบ 1 ใน 20 คน (ดังนั้นเราจะสามารถใช้ทรัพยากรของระบบได้เป็น 1/20) ก็หมายความว่าใน 1 วินาทีจะ execute คำสั่งได้หนึ่งล้าน instructions หรือสามารถเข้าถึงแผ่นจานแม่เหล็กได้ 6 ครั้ง

การใช้ binary search tree ที่ไม่สมดุลเป็นสิ่งไม่พึงประสงค์ ในกรณี worst case มีทรีมีความลึกเป็น linear และต้องใช้จำนวนครั้งของการเข้าถึงจานแม่เหล็กเป็นจำนวน 10 ล้านครั้ง สำหรับกรณีเฉลี่ยแล้ว การค้นหาค่าที่ประสบความสำเร็จต้องใช้การเข้าถึง disk จำนวน $1.38\ log\ N ครั้ง$ — ประมาณ 32 ครั้ง หรือ 5 วินาที ถ้าเราใช้ทรีแบบ AVL สำหรับกรณี worst case จะต้องใช้การเข้าถึงแผ่นจานแม่เหล็กเป็นจำนวน $1.44\ log\ N$ ครั้ง แต่โดยทั่วไปจะใกล้เคียงกับ $log\ N$ ดังนั้นต้องใช้การเข้าถึงแผ่นจานแม่เหล็กประมาณ 25 ครั้งโดยเฉลี่ย หรือประมาณ 4 วินาที

สิ่งที่เราต้องการคือจะต้องลดจำนวนครั้งของการเข้าถึงแผ่นจานแม่เหล็กลงให้เหลือ 3 หรือ 4 หรือ 5 ครั้งเท่านั้นซึ่งแน่นอนว่า binary search tree ไม่สามารถทำได้เพราะเราไม่สามารถไปได้ต่ำกว่า $log\ N$ ทางออกดูจะค่อนข้างชัดเจน คือ ถ้าโนดของทรีมีแขนงมากขึ้นก็หมายความว่าทรีนั้นก็จะมีความสูงน้อยลง ในขณะที่ทรีที่เป็น perfect binary tree ที่โนดทั้งสิ้น 31 โนด จะเป็นทรีที่มี 4 ระดับนั้นถ้าเป็นทรีที่เป็น 5-ary tree ที่มีจำนวนโนด 31 โนดเท่ากันนั้นจะมีเพียง 3 ระดับเท่านั้น ดังแสดงในรูปที่ 4.58 ทรีแบบ M-ary search tree จะสามารถมีจำนวนกิ่งแขนงได้ M กิ่ง ขณะที่จำนวนกิ่งเพิ่มขึ้นจะทำให้ความสูงลดลง และทรีที่เป็น complete M-ary tree จะมีความสูงประมาณ $log_M\ N$ เท่านั้น

เราสามารถสร้าง M-ary tree ได้ในลักษณะเดียวกับที่เราสร้าง binary search tree สำหรับ binary search tree เราต้องอาศัยค่า key 1 ค่าเพื่อตัดสินใจว่าจะใช้กิ่งแขนงใดหนึ่งในสองกิ่ง แต่ใน M-ary search tree, เราต้องใช้ค่า M – 1 ค่าในการตัดสินใจเลือกกิ่งที่จะเดินทางต่อไปในทรี เพื่อให้การทำงานตามที่กล่าวนี้มีประสิทธิภาพในกรณี worst case เราจะต้องประกันได้ว่า M-ary search tree จะต้องมีความสมดุล มิฉะนั้นแล้วทรีที่ได้อาจจะเสียหายจนมีลักษณะเป็นลิงค์ลิสต์

วิธีการหนึ่งที่ทำได้คือการใช้ B-tree ในที่นี้จะกล่าวถึง B-tree แบบพื้นฐานแบบหนึ่งเท่านั้น ในทางปฏิบัติ B-tree มีการใช้กันในหลายรูปแบบแตกต่างกันไปในบางประเด็นเท่านั้น แต่โดยรวมแล้วการใช้ B-tree ไม่ว่าแบบใดจะทำให้เราต้องเข้าถึงแผ่นจานแม่เหล็กเพียงไม่กี่ครั้งเท่านั้น

B-tree ที่มี order M คือ M-ary tree ที่มีคุณสมบัติดังต่อไปนี้

1. หน่วยข้อมูลเก็บอยู่ที่ leaves
2. โนดที่ไม่ใช่ leaf เก็บค่าได้เป็นจำนวน M – 1 ค่าเพื่อเป็นค่าชี้แนะในการค้นหา ค่าที่อยู่ที่ลำดับที่ i เป็นค่าที่น้อยที่สุดในทรีย่อยที่ตำแหน่งที่ i + 1
3. โนดที่เป็นรากอาจเป็นตัวโนดที่เป็น leaf เอง หรือไม่ก็เป็นโนดที่มีโนดลูกได้จำนวนระหว่าง 2 ถึง M โนด
4. โนดที่ไม่ใช่ leaf ทั้งหมด (ยกเว้นโนดราก) มีโนดลูกได้ตั้งแต่ $⌈\frac{M}{2}⌉$ ถึง M โนด
5. โนดที่เป็น leaves ทั้งหมดอยู่ในระดับความลึกเดียวกัน และมีค่าข้อมูลได้จำนวนตั้งแต่ $⌈\frac{L}{2}⌉$ ถึง L ค่า, สำหรับค่า L ใด ๆ ซึ่งจะกล่าวถึงวิธีการคำนวณหาค่าของ L อีกครั้งหนึ่ง

รูปที่ 4.59 แสดง B-tree ที่ order 5 จะเห็นว่าโนดที่ไม่ใช่ leaf ทุกตัวมีโนดลูกได้ตั้งแต่ 3 ถึง 5 โนด (ดังนั้นมันจึงมีจำนวนค่าได้ตั้งแต่ 2 ถึง 3 ค่า) โนดรากอาจมีโนดลูกได้จำนวนน้อยที่สุด 2 โนดเท่านั้น ในกรณีตัวอย่างทรีนี้มีค่า L = 5 (กรณีนี้ค่าของ L เท่ากันกับค่าของ M) เนื่องจาก L = 5 ดังนั้นโนดที่เป็น leaf แต่ละโนดจึงมีจำนวนค่าข้อมูลได้ตั้งแต่ 3 ถึง 5 ค่า

ถ้าแต่ละโนดในทรีแทนหนึ่ง disk block เราก็จะเลือกค่า M และ L โดยการใช้ขนาดของหน่วยข้อมูลที่จะจัดเก็บเป็นตัวพิจารณา เช่นสมมุติให้หนึ่งดิสค์บล็อกมีขนาด 8192 ไบต์ และจากตัวอย่างที่แล้ว ค่าแต่ละค่าใช้เนื้อที่ 32 ไบต์ ดังนั้น B-tree ที่มี order M ซึ่งจะต้องมีจำนวนค่าในหนึ่งโนดได้จำนวน M – 1 ค่า, ทั้งหมดในโนดจึงต้องใช้เนื้อที่เป็น 32M – 32 ไบต์ บวกกับขนาดกิ่งอีกจำนวน M กิ่ง และถ้าขนาดของแต่ละกิ่งต้องใช้เนื้อที่ 4 ไบต์ ดังนั้นจำนวนกิ่งทั้งหมดของโนดจึงใช้เนื้อที่รวม 4M ไบต์ นั่นคือเราต้องใช้ขนาดหน่วยความจำทั้งหมดที่ต้องการสำหรับโนดหนึ่งโนดที่ไม่ใช่ leaf คือ 36M – 32 ไบต์ ดังนั้น 36M – 32  8192 เราจะเลือกให้ M = 228 เนื่องจากว่าหนึ่งระเบียนใช้เนื้อที่ 256 ไบต์ ดังนั้นจึงบรรจุได้ 32 ระเบียนในหนึ่งดิสค์บล็อก เราจึงเลือกให้ L = 32 แต่ละโนดที่เป็น leaf มีจำนวนค่าข้อมูลได้ตั้งแต่ 16 ถึง 32 ระเบียนข้อมูลและโนดที่เป็น internal node (ยกเว้นโนดราก) มีกิ่งแยกได้อย่างน้อยที่สุด 114 ทาง เนื่องจากเรามี 10 ล้านระเบียน, ดังนั้นจึงใช้โนดที่เป็น leaf อย่างมากที่สุดจำนวน 625,000 โนด (คือ 10 ล้าน หารด้วย 16) ผลที่ได้คือ ในกรณี worst case โนดที่เป็น leaf จะอยู่ที่ระดับ 4 หรือกล่าวว่ากรณี worst case จำนวนครั้งที่ใช้ในการเข้าถึงโนดที่ต้องใช้โดยประมาณ คือ log M/2 N

ประเด็นที่เหลือคือการลบและการบรรจุหน่วยข้อมูลในทรี ในที่นี้จะกล่าวถึงการบรรจุค่าก่อน สมมติกรณีที่เราต้องการบรรจุค่า 57 เข้าใน B-tree ในรูปที่ 4.59 จากการสืบค้นลงไปในทรีไม่พบค่า 57 ดังนั้นจึงบรรจุลงในโนดที่เป็น leaf ดังรูปที่ 4.60

การบรรจุค่า 57 ดูจะเป็นเรื่องง่ายเนื่องจากโนดที่เป็น leaf ที่จะบรรจุค่านั้นยังมีที่ว่างให้ทำเช่นนั้นได้ ถ้าเราต้องการบรรจุค่า 55 ลงในทรีในเวลานี้ ก็จะพบว่าโนดที่ต้องบรรจุค่า 55 ลงไปนี้มีจำนวนข้อมูลเต็มอยู่แล้ว (ดูรูปที่ 4.60) อย่างไรก็ตามการแก้ปัญหาก็ไม่ได้ยุ่งยาก เนื่องจากที่โนดดังกล่าวนี้มีจำนวนค่าอยู่แล้ว L + 1 ค่า, จึงต้องแยกโนด leaf นี้ออกเป็น 2 โนด โดยต้องประกันได้ว่าแต่ละโนดใหม่นั้นต้องมีจำนวนค่าในจำนวนน้อยที่สุดที่ยอมให้มีได้ตามข้อกำหนดของทรี เราจึงสร้างโนดใหม่แต่ละตัวให้มีจำนวนข้อมูลในโนด 3 ข้อมูล เราต้องใช้จำนวนการเข้าถึงแผ่นจานแม่เหล็ก 2 ครั้งเพื่อการเขียนโนด leaf ทั้งสองนี้และใช้การเข้าถึงอีกหนึ่งครั้งสำหรับการปรับเปลี่ยนโนดแม่ของมัน ในโนดแม่ดังกล่าวนี้ต้องมีการเปลี่ยนแปลงขึ้นทั้งค่าในโนดและแขนงกิ่งเองดังรูปที่ 4.61 ถึงแม้ว่าการแบ่งแยกโนดต้องใช้เวลาในการทำงานเนื่องจากอย่างน้อยมันต้องใช้การเข้าถึงจานแม่เหล็กเพิ่มเติมขึ้น 2 ครั้ง แต่ก็เป็นเหตุการณ์ที่เกิดขึ้นไม่บ่อยนัก เช่น ถ้า L = 32 และเมื่อมีการแบ่งแยกออกเป็น 2 โนดที่ต้องมีจำนวนค่าอยู่ในโนด 16 และ 17 ตัว กล่าวสำหรับโนดใหม่ที่มีค่าอยู่ 17 ตัวนั้นเราก็จะยังคงสามารถทำการบรรจุค่าเพิ่มได้อีกถึง 15 ค่าโดยไม่ต้องแบ่งแยกโนดใหม่อีกเลย หรือกล่าวอีกอย่างได้ว่า ทุก ๆ การแบ่งแยกโนดก็จะไม่ต้องทำการแบ่งแยกใหม่อีกประมาณ L/2 ครั้ง

การแบ่งแยกโนดตามตัวอย่างที่ผ่านมานี้ทำได้ง่าย เนื่องจากโนดแม่ของมันยังมีโนดลูกไม่เต็มจำนวน ต่อจากนี้ถ้าเราต้องการบรรจุค่า 40 เข้าในรูปทรีรูปที่ 4.61 ก็หมายความว่าเราต้องทำการนแบ่งแยกโดน leaf ที่มีค่า 35 ถึง 39 อยู่ และต้องบรรจุค่า 40 ลงไปด้วยนี้ออกเป็นสองโนด ซึ่งจะทำให้โนดแม่ของมันจะมีโนดลูกรวมเป็นจำนวน 6 โนด โดยที่ตามนอยามของ B-tree ที่มี order 5 จะอนุญาตให้มีได้โนดลูกได้เพียง 5 โนดเท่านั้น ดังนั้นจึงต้องทำการแยกโนดแม่นี้ออกเป็น 2 โนด พร้อมทั้งปรับปรุงค่าที่อยู่ภายในตัวโนดแม่พร้อมทั้งค่าที่อยู่ภายในโนดแม่ของโนดแม่นี้ด้วย ผลที่ได้แสดงในรูปที่ 4.62 เมื่อมีการแยกโนดแม่ทำให้ต้องมีการเขียนบล็อกของจานแม่เหล็กเพิ่มขึ้นอีก 2 ครั้ง (ดังนั้นการบรรจุค่านี้จึงต้องใช้การเขียนจานแม่เหล็ก 5 ครั้ง)

กรณีที่เมื่อโนดที่ไม่เป็น leaf (nonleaf) มีการแยกโนดเกิดขึ้นดังกรณีที่กล่าวข้างบนนี้ ก็หมายความว่าโนดแม่ของมันจะมีจำนวนโนดลูกเพิ่มขึ้น สำหรับกรณีที่โนดแม่นั้น ๆ มีจำนวนโนดลูกค่าเต็มจำนวนที่จำกัดแล้ว เราก็จะทำการแบ่งแยกโนดเป็นลำดับขึ้นไปในทรีจนกระทั่งถึงโนดแม่ที่ไม่จำเป็นต้องแบ่งแยกออกอีกหรือไม่ก็จะต้องทำขึ้นไปจนกระทั่งถึงโนดราก และถ้าเราจำเป็นต้องทำการแยกโนดรากออกเป็น 2 โนด เราสามารถทำได้โดยการสร้างโนดที่จะเป็นโนดรากโนดใหม่ขึ้นและกำหนดให้มีโนดทั้งสองที่แยกมานั้นเป็นโนดลูกของโนดรากใหม่นี้ และมีเพียงกรณีที่กล่าวนี้เท่านั้นที่จะทำให้ความสูงของ B-tree เพิ่มมากขึ้นได้

ยังมีวิธีการอื่น ๆ ในการจัดการกับกรณีโนดหนึ่ง ๆ มีโนดลูกมากเกิดข้อกำหนด วิธีการที่ใช้กันอยู่วิธีการหนึ่งคือการนำค่าในโนดลูกค่าหนึ่งไปให้โนดข้างเคียงที่ยังมีที่ว่างพอ เช่น ถ้าต้องการบรรจุ 29 ลงในทรีรูปที่ 4.62 เราสามารถจัดให้มีที่ว่างในโนดที่บรรจุมันได้ด้วยการย้ายค่า 32 ไปให้โนดข้างเคียงและปรับปรุงค่าที่อยู่ในโนดแม่ของมัน

การลบค่าออกจากทรีทำได้ด้วยการหาที่ต้องการลบให้พบเสียก่อนจากนั้นจึงทำการลบค่าออกจากโนด (ค่าอยู่ในโนดที่เป็น leaf) ปัญหาที่อาจจะตามมาเมื่อมีการลบค่าออกจากโนดที่เป็น leaf แล้ว อาจทำให้โนด leaf นั้น ๆ มีจำนวนข้อมูลน้อยกว่าจำนวนต่ำสุดที่ยอมให้มีได้ของทรีนั้น กรณีนี้เราอาจปรับปรุงได้ด้วยการนำค่าจากในโนดข้างเคียงมาเพิ่มถ้าโนดข้างเคียงมีจำนวนหน่วยข้อมูลมากกว่าจำนวนต่ำสุดที่ยอมให้มีในโนด แต่ถ้าโนดข้างเคียงก็มีจำนวนค่าเป็นจำนวนต่ำสุดอยู่แล้ว เราก็สามรถแก้ปัญหาได้ด้วยการควบรวมโนดนี้เข้ากับโนดข้างเคียงนั้น แต่การทำเช่นนี้ก็จะทำให้โนดแม่ของมันสูญเสียจำนวนโนดลูกไป และถ้าการเสียโนดลูกไปนี้ทำให้โนดแม่เหลือโนดลูกในจำนวนที่ต่ำกว่าจำนวนต่ำสุดที่ยอมให้มีได้ตามข้อกำหนดของทรีก็หมายความว่าเราต้องดำเนินการกระบวนการเช่นเดิมที่กล่าวมานี้กับโนดแม่นั้น ๆ กระบวนการดำเนินการดังกล่าวนี้อาจจะเกิดขึ้นกับโนดขึ้นไปเรื่อย ๆ จนถึงโนดรากซึ่งในภาวะเช่นนี้ก็หมายความว่าโนดรากจะมีโนดลูกเพียงโนดเดียว เราก็เพียงแต่ตัดโนดรากเดิมทิ้งไปและใช้โนดลูกของมันเป็นโนดรากใหม่แทน เช่นถ้าต้องการลบค่า 99 จากทรีในรูปที่ 4.62 จะทำให้ในโนดนั้นมีค่าเหลืออยู่ 2 ค่า และโนดข้างเคียงมีจำนวนค่าต่ำสุดอยู่จึงสามารถควบรวมเข้าด้วยกันได้เป็นโนด leaf ใหม่ที่มีจำนวน 5 ค่า แต่ทำให้โนดแม่ของมันที่จำนวนโนดลูกเหลือเพียง 2 โนด อย่างไรก็ตามโนดข้างเคียงมันมีจำนวนโนดลูกอยู่ 4 โนด มันจึงสามารถยืมโนดลูกมาได้ 1 โนด ทำให้โนดทั้งสองมรจำนวนโนดลูกเป็น 3 เท่ากันดังรูปที่ 4.63