Tree ใน Data Structures - B-Tree คืออะไร

 

ในโลกของการจัดการข้อมูลและอัลกอริธึม ไม่สามารถไม่กล่าวถึง "Tree" ซึ่งถือเป็นโครงสร้างข้อมูลพื้นฐานที่มีบทบาทในการวิเคราะห์และจัดเก็บข้อมูล โดยหนึ่งในประเภทของ Tree ที่มีความสำคัญอย่างมากคือ "B-Tree" ซึ่งเป็นโครงสร้างที่ใช้ในการจัดการข้อมูลจำนวนมากอย่างมีประสิทธิภาพในฐานข้อมูลและระบบไฟล์ต่าง ๆ

 

ทำความรู้จักกับ Tree เบื้องต้น

Tree หรือ โครงสร้างข้อมูลต้นไม้ เป็นโครงสร้างที่ประกอบไปด้วย "โหนด" (Nodes) ที่เชื่อมต่อกันโดย "เส้น" (Edges) โดยมีโหนดหลักหนึ่งตัวที่ทำหน้าที่เป็น "ราก" (Root) ทุกโหนดสามารถมีลูกได้หลายโหนดแต่มีพ่อเพียงหนึ่งเสมอ

ประเภทของ Tree

1. Binary Tree: เป็นประเภทที่แต่ละโหนดมีลูกไม่เกินสองโหนด ใช้บ่อยในงานประเภทค้นหาและเรียงลำดับ 2. Binary Search Tree (BST): เป็น Binary Tree ที่มีคุณสมบัติพิเศษคือ โหนดซ้ายจะมีค่าน้อยกว่าโหนดแม่ และโหนดขวาจะมีค่ามากกว่า 3. B-Tree: เป็น Tree ที่ออกแบบมาเพื่อทำงานกับดิสก์และจัดการข้อมูลจำนวนมากอย่างมีประสิทธิภาพ

บทความนี้จะเน้นไปที่ B-Tree ซึ่งมีบทบาทสำคัญในฐานข้อมูลและระบบไฟล์

 

B-Tree คืออะไร

B-Tree (Balanced Tree) ริเริ่มพัฒนาโดย Rudolf Bayer และ Ed McCreight ในปี ค.ศ. 1972 เป็นโครงสร้างข้อมูล Tree ชนิดหนึ่ง ซึ่งมีคุณสมบัติเพิ่มความสมดุลของ Tree พร้อมทั้งเพิ่มประสิทธิภาพในการเข้าถึงข้อมูล เพราะว่า B-Tree สามารถรักษาความสมดุลของข้อมูลในขณะที่มีการแทรกและลบได้ดี

 

คุณสมบัติของ B-Tree

1. การเป็นสมดุล: ทุกๆ ใบของ B-Tree จะอยู่ในระดับเดียวกัน 2. Node จะมีค่าอยู่ในช่วง [t-1, 2t-1]: ยกเว้น Root ที่อาจมีน้อยที่สุด เนื่องจาก t คือค่า minimium degree หรือว่ากิ่งอยู่ที่ไหน 3. การแทรกและลบมีค่าเฉลี่ย O(log n): การกระทำทั้งสองในโครงสร้างข้อมูลนี้สามารถทำได้ในลอการิทึมของขนาดข้อมูลเสมอ 4. การแยก Node (Split): เมื่อ Node อิ่มตัวจะถูกแยกเป็นสอง Node ซึ่งจะรักษาสมดุลของ Tree ได้

 

การทำงานของ B-Tree

การแทรกข้อมูล

เมื่อมีการแทรกข้อมูล ระบบจะตรวจสอบว่าโหนดนั้นเต็มหรือยัง ถ้าไม่เต็มจะทำการแทรกโดยตรง แต่ถ้าเต็มจะทำการแยกและกระจายข้อมูลขึ้นไปยังระดับที่สูงกว่า โดยกระบวนการนี้ทำในเวลาคงที่ O(log n)

การลบข้อมูล

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

 

ตัวอย่างโค้ด B-Tree

ต่อไปนี้คือตัวอย่างการสร้างโครงสร้าง B-Tree แบบง่าย ๆ ในภาษา Python:

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t, True)
        self.t = t

    def traverse(self, node):
        for i in range(len(node.keys)):
            if not node.leaf:
                self.traverse(node.children[i])
            print(node.keys[i], end=' ')
        if not node.leaf:
            self.traverse(node.children[len(node.keys)])

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode(self.t)
            new_root.children.append(root)
            new_root.leaf = False
            self.split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, k)

    def split_child(self, parent, i):
        t = self.t
        y = parent.children[i]
        z = BTreeNode(t, y.leaf)

        parent.children.insert(i + 1, z)
        parent.keys.insert(i, y.keys[t - 1])

        z.keys = y.keys[t:(2 * t) - 1]
        y.keys = y.keys[:t - 1]

        if not y.leaf:
            z.children = y.children[t:2 * t]
            y.children = y.children[:t]

    def _insert_non_full(self, node, k):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(0)
            while i >= 0 and node.keys[i] > k:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = k
        else:
            while i >= 0 and node.keys[i] > k:
                i -= 1
            i += 1
            if len(node.children[i].keys) == (2 * self.t) - 1:
                self.split_child(node, i)
                if node.keys[i] < k:
                    i += 1
            self._insert_non_full(node.children[i], k)

# ทดสอบการทำงานของ B-Tree
btree = BTree(3)  # ค่า t = 3
keys = [10, 20, 5, 6, 12, 30, 7, 17]

for key in keys:
    btree.insert(key)

print("Traversal of the B-Tree:")
btree.traverse(btree.root)

 

สรุป

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

การมีพื้นฐานความเข้าใจ B-Tree จะเป็นประโยชน์อย่างมากสำหรับผู้ที่มีความสนใจเกี่ยวกับการพัฒนาและการจัดการข้อมูลในระดับสูง ผู้ที่สนใจสามารถศึกษา B-Tree ต่อได้ที่สถาบัน Expert-Programming-Tutor (EPT) ที่ซึ่งมีทั้งคอร์สเรียนออนไลน์และการเรียนรู้แบบเจาะลึกที่สามารถพัฒนาทักษะและความเข้าใจในเรื่องนี้ให้ดียิ่งขึ้น

 

 

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

หากเจอข้อผิดพลาด หรือต้องการพูดคุย ติดต่อได้ที่ https://m.me/expert.Programming.Tutor/