โครงสร้างข้อมูลแบบ BTree

Home Page  |   รายการบทความ   |   ลิงค์ที่เกี่ยวข้อง   |   laploy.com  |  เกี่ยวกับผู้เขียน

 
โครงสร้างข้อมูลแบบ BTree

 

โปรแกรม SQL2008 จัดเก็บ NCI (Non-Clustered Index ดูรายละเอียดในหนังสือ เรียนรู้ด้วยตนเอง DataBase) โดยใช้โครงสร้างแบบ BTree การศึกษาทำความเข้าใจหลักการ BTree จะช่วยให้ท่านเข้าใจการทำงานของดรรชนีได้ดีขึ้น ดังนั้นในหัวข้อนี้ผู้เขียนจะอธิบายการทำงานของ BTree โดยสังเขป

โหนดราก (Root Node)

BTree ก็เหมือนโครงสร้างข้อมูลทั่วไปคือมีโหนด (node) เป็นองค์ประกอบพื้นฐาน BTree มีโครงสร้างเป็นลำดับชั้น โดยโหนดที่อยู่ในระดับบนสุด (หรือจะว่าเป็นระดับต่ำสุดก็ได้ขึ้นอยู่กับมุมมอง) เรียกว่าโหนดราก (Root Node ย่อ RN) ภายใน RN ประกอบด้วยตัวชี้หรือพอยน์เตอร์ (Pointer) ที่ชี้ไปยังโหนดอื่นๆ ซึ่งอยู่ในระดับต่ำกว่า เราเรียกโหนดพวกนี้ว่าโหนดในระดับใบ นอกจากนั้นเราอาจเรียกโหนดที่อยู่ระดับสูงกว่าว่า "โหนดแม่" และโหนดในระดับต่ำกว่าว่า "โหนดลูก"

 

โหนดราก (Root Node)

 

โหนดระดับใบ (Leaf Level Node)

โหนดระดับใบ (Leaf Level Node LLN) คือโหนดระดับต่ำสุดของโครงสร้างต้นไม้ BTree คือเป็นโหนดที่เก็บตัวข้อมูลจริงๆ หรือเก็บพอยน์เตอร์ที่ชี้ไปยังข้อมูล ไม่ได้เก็บพอยน์เตอร์ที่ชี้ไปยังพอยน์เตอร์

 

โหนดที่ไม่ใช่ระดับใบ (Non-Leaf Level Node)

ในการใช้งานทั่วไปฐานข้อมูลจะมีข้อมูลอยู่มากเกินกว่าที่ RN จะเก็บพอยน์เตอร์ได้หมดภายในโหนดเดียว โปรแกรม SQL2008 จึงต้องแตก RN ออกเป็นโหนดย่อยๆ อีกหนึ่งระดับ การแตกแขนงของกิ่งนี้คือการแบ่งหน้า (หรือ Page Split ที่ท่านเรียนไปแล้ว) โหนดที่เกิดขึ้นใหม่นี้ไม่ใช่ RN และ LLN จึงเรียกรวมๆ ว่าโหนดที่ไม่ใช่ระดับใบ (Non-Leaf Level Node ย่อ NLLN)

โหนดที่ไม่ใช่ระดับใบ (Non-Leaf Level Node) และ โหนดระดับใบ (Leaf Level Node)

 

ขั้นตอน PS

อย่างที่เรียนไปแล้วว่าเมื่อเกิด PS โปรแกรม SQL2008 จะย้ายแถวข้อมูลประมาณครึ่งหนึ่งจากเพจเก่าไปยังเพจใหม่ (ดูรายละเอียดในหนังสือ เรียนรู้ด้วยตนเอง DataBase)  สาเหตุที่ต้องทำเช่นนั้นเพราะต้องการรักษาสมดุลของ BTree ให้โหนดทางซ้ายและทางขวามีขนาดเท่ากัน SQL2008 ทำ PS ด้วยขั้นตอนดังนี้

  1. สร้างเพจใหม่
  2. ย้ายแถวข้อมูลจากเพจเดิมไปใส่เพจใหม่
  3. เพิ่มแถวข้อมูลใหม่เข้าสู่เพจ
  4. เพิ่มรายการ (เป็นพอยน์เตอร์) ในโหนดแม่

การแยกหน้า (Page Split) เมื่อเพจเต็ม

 

โฆษณา

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  เปลี่ยนแปลง )

Google photo

You are commenting using your Google account. Log Out /  เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out /  เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out /  เปลี่ยนแปลง )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: