Please enable JavaScript.
Coggle requires JavaScript to display documents.
Multiway tree (โครงสร้างข้อมูลมัลติเวย์ทรี) - Coggle Diagram
Multiway tree
(โครงสร้างข้อมูลมัลติเวย์ทรี)
ฺB-Tree vatiation
ฺB*tree
เมื่อเกิด overflow จะจัดเรียงโหนดใหม่
ถ้า sibling เต็มก็จะสามารถแบ่งดหนดใหม่ได้
utilization ประมาณ2/3 หรือ 66%
B+tree
leaf เก็บข้อมูล
node อื่นๆ เก็บ key เรียก index set
เข้าถึงข้อมูลได้ทั้งแบบลำดับ และแบบโดยตรง
Binary tree
Outdegree มีได้ไม่เกิน2
แต่ละNode เก็บข้อมูลได้ 1 เรคคอร์ด
ถ้าข้อมูลมาก level จะสูงตาม
Multiway tree
outdegree มีได้มากกว่า2
แต่ละ Node สามารถเก็บได้มากกว่า 1 เรคคอร์ด
คุณสมบัติ M-way search Tree
Each node has 0 m subtree
n subtree,n-1 data entries
โครงสร้างของ M-way node
B-tree
มี Root 2 subtree
Node อื่นๆ มี m/2 m subtrees
Leaf ทั้งหมดอยู่ใน level เดียวกัน
B-tree 5 order
root มี 2-5 subtrees
อื่นๆมี3-5 subtrees
Leaf ทั้งหมดอยู่ใน levelเดียวกัน
การเพิ่มข้อมูล B-tree
เพิ่มที่ leaf
ถ้าเกิน Max ให้ spilt เป็น 2 node และดึงตัวกลางไปไว้ที่ parent
การลบข้อมูลใน B-tree
กรณีข้อมูลเก็บอยู่ใน leaf
ลบ entry
shift left
ถ้า underflow จะต้อง Balance
กรณีข้อมูลเก็บอยู่ใน Nonleaf
ลบ entry
นำ entry ที่ใหญ่ที่ใหญ่ที่สุดทางซ้ายมาแทน
ถ้า underflow จะต้อง balance
slmplified B-tree
2-3 tree = order 3
2-3-4 tree = order 4
อินเด็ก(index)
เป็นกลไกลที่เพิ่มความเร็วในการเข้าถึงข้อมูลที่ต้องการ
จะประกอบด้วยเรคคอร์ด ซึ่งถูกเรียกว่า index entries
มีส่วนประกอบ 2 ส่วน คือ
Search key
pointer
โดยทั่วไป index จะมีขนาดเล็กกว่า แฟ้มข้อมูล
อินเด็กพื้นฐานมีอยู่ 2 ชนิด
odered indices
hash indices
อินเด็กแบบเรียงลำดับ (Ordered index) :star:
ordered index คือ index entries ที่จัดเก็บเรียงตาม search key
primary index คือ index ที่มีการจัดเรียง search key ตรงกับการจัดเรียงของข้อมูลในไฟล์
secondary index คือ index ที่ search key มีการจัดเรียงลำดับแตกต่างการจัดเรียงข้อมูลในไฟล์ลำดับ
index sequential file คือ ไฟล์เรียงตามข้อมูล primary index
Sparse Index Files
Sparse Index:
index ที่มีเรคคอร์ดบาง search key เท่านั้น
ใช้ได้ในกรณีที่ไฟล์มีการเรียงลำดับเรคคอร์ด
การค้นหาเรคคอร์ดที่ search key ที่มีค่า k
ค้นหา index reccord ที่มีค่ามากที่สุด ที่น้อยกว่า ค่า k
ค้นหา ไฟล์แบบลำดับ โดยเริ่มตำแหน่ง อินเด็กในข้อ 1 ชี้อยู่ไปจนกว่าจะพบ
primary และ secodary index
index ช่วยในเรื่องค้นหาที่เป็นรูปธรรม
แต่การอัพเดต indexจะทำให้เกิดการ overhead บนฐานข้อมูล
แสกนแบบลำดับ(seqeuntial scan)โดยใช้ primary index จะมีประสิทธิภาพ
การเข้าถึงเรคคอร์ดข้อมูล อาจจะต้องทำการ fetch ข้อมูลบล็อกใหม่จากดิสก์
index กับฐานข้อมูล (mySQL)
การสร้าง index ในขั้นตอนของการสร้างตาราง
การสร้าง index ภายหลังจากการสร้างตาราง
prefrix index mysql
Descending Index (MySQL)
การสร้าง index ด้วยการแก้ไขตาราง mysql
การลบ index (MySQL)
