CoE KKU

หัวข้อสุดท้ายที่จะกล่าวถึงในบทนี้คือกรณีที่จำนวนข้อมูลมีปริมาณมากเกินกว่าที่จะบรรจุลงในหน่วยความหลักได้ทั้งหมด ดังที่ได้กล่าวไปแล้วในบทที่ 4 ว่าสิ่งที่จะต้องให้ความสนใจในกรณีเช่นนี้ คือจำนวนครั้งในการเข้าถึงแผ่นจานแม่เหล็กที่เราต้องการอ่านเขียนหรือค้นหาข้อมูล

สมมุติ เรามีข้อมูลอยู่จำนวน N รายการที่จะต้องจัดเก็บ ณ เวลาหนึ่ง ซึ่งค่า N นี้จะเปลี่ยนไปตามเวลาที่ใช้งาน และเรากำหนดให้ disk block หนึ่งสามารถจุข้อมูลได้ M รายการ ในหัวข้อนี้เราจะใช้ M = 4 ปัญหาที่จะเกิดขึ้นถ้าเราเลือกใช้โครงสร้างข้อมูลแบบตารางแฮชทั้งที่เป็น open hashing หรือ closed hashing ก็คือ เมื่อเกิดการชนขึ้นก็อาจจะทำให้ต้องมีการอ่านบล็อกจำนวนมากเพื่อการค้นหา (find) ถึงแม้จะเป็นตารางที่มีการกระจายของข้อมูลที่ดีก็ตาม ยิ่งไปกว่านั้น เมื่อตารางใกล้เต็ม และต้องใช้การ rehash ก็จะต้องใช้จำนวนการเข้าถึง disk block เป็น $O(N)$ บล็อก ซึ่งเป็นสิ่งที่ไม่พึงประสงค์

Extendible hashing มีการทำงานของ find ด้วยการเข้าถึง disk เพียงสองครั้ง การบรรจุค่าก็เข้าถึง disk เพียงไม่กี่ครั้ง สำหรับโครงสร้างแบบ B-tree แล้วก็จะมีความลึกเป็น $O(log_{M/2}⁡N)$ และเมื่อ M มีค่าเพิ่มขึ้นความลึกของ B-tree ก็จะลดลง ดังนั้นในทางทฤษฎีแล้ว เราก็อาจจะเลือกให้ M มีค่ามากจนกระทั่งความลึกของ B-tree ดังกล่าวนั้นมีค่าเท่ากับ 1 และการทำงาน find การอ่านบล็อกแรกแล้วก็จะอ่านบล็อกอีกครั้งเท่านั้น ถ้าสมมติให้โนดรากทั้งโนดของมันสามารถเก็บในหน่วยความหลักได้ ปัญหาของวิธีที่กล่าวนี้ คือ จำนวนกิ่งแขนงมีเป็นจำนวนสูงมากและต้องใช้เวลาการทำงานนานมากเพื่อตัดสินใจว่าโนดที่เป็น leaf โนดใดที่มีข้อมูลที่ต้องการ และถ้าเวลาที่ต้องใช้ในขั้นตอนที่กล่าวนี้สามารถทำให้ลดลงได้ก็จะเป็นวิธีที่น่านำมาใช้ได้ในทางปฏิบัติ วิธีที่จะทำเช่นที่กล่าวนี้ได้คือวิธีที่เรียกว่า extendible hashing

สมมติให้ข้อมูลที่เรามีสามารถเขียนแทนได้ด้วย six-bit integers รูปที่ 5.23 แสดง extendible hashing ของข้อมูลนี้ รากของ “tree” มีตัวเชื่อมต่อ (link) 4 ตัวที่นำมาจากสองบิตแรกของชุดข้อมูล แต่ละ leaf มีข้อมูลสมาชิกได้สูงสุดถึง M = 4 ตัว จะเห็นว่าค่าข้อมูลในแต่ละ leaf เดียวกันมีสองบิตแรกเหมือนกันซึ่งระบุได้ด้วยตัวเลขในวงเล็บ หรือกล่าวว่า ถ้า D แทนจำนวนบิตที่ใช้ในโนดราก (เรียกว่า directory) จำนวนรายการที่สามารถบรรจุได้ใน directory ก็จะเป็น 2D รายการ ตัวเลข dL เป็นจำนวนบิตนำหน้าของข้อมูลที่ทุกสมาชิกใน leaf L มีค่าเหมือนกัน ค่าของ dL จะเป็นเท่าใดนั้นขึ้นอยู่กับว่ามันเป็น leaf ใด, และ dL < D

ถ้าเราต้องการบรรจุค่า 100100 ค่านี้ก็จะต้องถูกจัดอยู่ใน leaf ที่ 3 แต่เนื่องจาก leaf ที่ 3 นี้ไม่มีที่ว่างพอเนื่องมีจำนวนข้อมูลเต็มความจุแล้วทำให้ต้องแยกโนดนี้ออกเป็น 2 โนดโดยที่ต้องนำบิตที่ 3 ของข้อมูลมาร่วมใช้ในการพิจารณาด้วย และยังจะต้องเพิ่มขนาดของ directory ขึ้นเป็น 3 บิต ผลการทำงานนี้แสดงในรูปที่ 5.24

จะสังเกตเห็นว่าโนดที่เป็น leaf ใดที่ไม่เกี่ยวข้องกับการแบ่งแยกโนดก็จะมีตัวเชื่อมต่อของ directory มาจาก 2 รายการ ถ้าต้องการบรรจุค่า 000000 ก็จะต้องแยกโนดแรกเป็น 2 โนดที่มี dL = 3 เนื่องจาก D = 3 การปรับเปลี่ยนที่เกิดขึ้นใน directory คือการเปลี่ยนตัวเชื่อมต่อของ 000 และ 001 เท่านั้น ดังแสดงในรูปที่ 5.25