ต้นไม้แบบที

ตัวอย่างต้นไม้แบบที

ในสาขาวิชาวิทยาการคอมพิวเตอร์ ต้นไม้แบบที (T-tree) เป็นโครงสร้างข้อมูลประเภท ต้นไม้ทวิภาค ที่ถูกใช้เป็น ฐานข้อมูลหน่วยความจำหลัก (main-memory database) เช่น Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen และ Kairos

ต้นไม้แบบที เป็นต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) เหมาะสำหรับกรณีที่หน่วยความจำเก็บทั้งดัชนีและข้อมูลเช่นเดียวกับ ต้นไม้แบบบี (B-tree) ที่เหมาะสำหรับการรักษาข้อมูลของหน่วยความจำสำรอง เช่น ฮาร์ดดิสก์ นอกจากนี้ต้นไม้แบบทียังได้ประโยชน์จากโครงสร้างหน่วยความจำแบบต้นไม้เช่นเดียวกับ ต้นไม้เอวีแอล (AVL tree) ในขณะที่สามารถประหยัดพื้นที่เก็บข้อมูลเมื่อมีขนาดเป็นจำนวนมากได้ เพราะว่าแต่ละปมของต้นไม้เอวีแอลสามารถเก็บข้อมูลได้เพียงแค่ตัวเดียว จึงจำเป็นที่ต้องสร้างปมเพื่อเก็บข้อมูลเป็นจำนวนมากกว่า

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

ชื่อ ต้นไม้แบบที มาจากรูปร่างของปมที่มีลักษณะเหมือนตัวอักษรในภาษาอังกฤษตัว T[1]

ประสิทธิภาพ

แม้ว่าต้นไม้แบบทีจะถูกนำมาใช้กันอย่างแพร่หลายสำหรับฐานข้อมูลหน่วยความจำหลัก แต่การวิจัย[2][3]เมื่อเร็วๆ นี้แสดงให้เห็นว่าจริงๆ แล้วมันไม่ได้ทำงานได้ดีกว่า ต้นไม้แบบบี เลย เมื่อใช้กับฮาร์ดแวร์สมัยใหม่

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

โครงสร้างปม

โครงสร้างปมของต้นไม้แบบที

ต้นไม้แบบที ประกอบจะประกอบไปด้วย ตัวชี้ไปยังปมพ่อ ตัวชี้ไปยังปมลูกซ้ายและขวา แถวลำดับของตัวชี้ข้อมูล และข้อมูลการควบคุมพิเศษ

ปมที่มีต้นไม้ย่อย (subtree) สองต้น เรียกว่า ปมภายใน (internal nodes) ปมที่ไม่มีต้นไม้ย่อย เรียกว่า ปมใบ (leaf nodes) และปมที่มีต้นไม้ย่อยเพียงแต่ต้นเดียว เรียกว่า ปมครึ่งใบ (half-leaf nodes) ปมจะถูกเรียกว่า ปมขอบเขต (bounding node) สำหรับค่าหนึ่ง ถ้าค่านั้นอยู่ระหว่างค่าน้อยสุดและมากสุดของปมนั้น

ค่าขอบเขต

ค่าที่มากที่สุดในต้นไม้ย่อยซ้ายของแต่ละปมภายใน เรียกว่า ขอบเขตล่างมากสุด (greatest lower bound) ค่าที่น้อยที่สุดในต้นไม้ย่อยขวาของแต่ละปมภายใน เรียกว่า ขอบเขตบนน้อยสุด (least upper bound) ซึ่งค่าทั้งสองนี้จะอยู่ที่ปมใบหรือปมครึ่งใบเสมอ ปมใบและปมครึ่งใบสามารถมีจำนวนข้อมูลได้ตั้งแต่หนึ่งจนถึงขนาดของแถวลำดับข้อมูล แต่จำนวนข้อมูลขั้นต่ำและมากสุดของปมภายในจะถูกกำหนดไว้ล่วงหน้าแล้ว

การสร้างบริการ

การค้นหาสมาชิก

• เริ่มค้นที่ปมราก
• ถ้าปมนั้นเป็นปมขอบเขตสำหรับค่าที่ต้องการหา จึงค้นค่าในแถวลำดับของข้อมูลของปมนั้น ถ้าไม่พบแสดงว่าไม่มีค่านั้นอยู่
• ถ้าค่าที่ต้องการหามีค่าน้อยกว่าค่าน้อยสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยซ้ายของมัน ถ้าไม่มีต้นไม้ย่อยซ้ายแสดงว่าไม่มีค่านั้นอยู่
• ถ้าค่าที่ต้องการหามีค่ามากกว่าค่ามากสุดของปมนั้น ให้ค้นต่อที่ต้นไม้ย่อยขวาของมัน ถ้าไม่มีต้นไม้ย่อยขวาแสดงว่าไม่มีค่านั้นอยู่

การเพิ่มสมาชิก

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

ถ้ามีการเพิ่มปมใหม่ ต้นไม้อาจจำเป็นต้องปรับสมดุล (rebalanced) จะอธิบายด้านล่าง

การลบสมาชิก

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

การหมุนและการปรับสมดุล

ต้นไม้แบบทีจะดำเนินการบนพื้นฐานของ ต้นไม้ค้นหาแบบทวิภาคที่มีโครงสร้างปรับสมดุลเองได้ (Self-balancing binary search tree) โดยเฉพาะตามที่บทความของ Lehman และ Carey[1] ได้อธิบายไว้ว่าต้นไม้แบบทีจะปรับสมดุลเหมือนกับต้นไม้เอวีแอล ที่ว่ามันจะไม่สมดุลเมื่อปมลูกมีความสูงต่างกันอย่างน้อยสองระดับ กรณีนี้จะเกิดขึ้นหลักจากทำการเพิ่มหรือลบปม ซึ่งหลังจากทำการเพิ่มหรือลบปมแล้ว ต้นไม้จะถูกตรวจจากใบไปยังราก ถ้าตรวจพบว่าไม่สมดุลก็จะทำการหมุนหนึ่งหรือสองครั้ง ทำให้สามารถประกันได้ว่าต้นไม้จะสมดุลเสมอ

เมื่อหมุนเสร็จแล้วปมภายในมีจำนวนข้อมูลน้อยกว่าขั้นต่ำที่ใส่ได้ให้ย้ายข้อมูลจากปมลูกมาใส่ในปมภายในนี้ (อาจมากกว่าหนึ่งปม)

ดูเพิ่ม

• โครงสร้างข้อมูล
• ต้นไม้ (โครงสร้างข้อมูล)

ต้นไม้แบบอื่น

• ทรีพ
• ต้นไม้แดงดำ
• ต้นไม้บาน

อ้างอิง

1. Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986
2. Rao, Jun; Kenneth A. Ross (1999). "Cache conscious indexing for decision-support in main memory" . Proceedings of the 25th International Conference on Very Large Databases (VLDB 1999). Morgan Kaufmann. pp. 78–89.
3. Kim, Kyungwha; Junho Shim, and Ig-hoon Lee (2007). "Cache conscious trees: How do they perform on contemporary commodity microprocessors?". Proceedings of the 5th International Conference on Computational Science and Its Applications (ICCSA 2007). Springer. pp. 189–200.