Hierarchical Data in Database

ปกติผมจะเก็บ tree structure ใน db ด้วย schema แบบนี้

create table foo (
    id long,
    ....
    parent_id long
)

ซึ่งก็ ok แหล่ะ แต่การท่อง tree หรือหา path ของ tree ค่อนข้างกิน io ไปนิด
ซึ่งปกติที่ทำก็คือ load ทั้งหมดมา build เป็น graph structure แล้วเก็บ
มันไว้ใน cache

วันนี้ไปอ่านเจอที่ Gijs Van Tulder เขียนไว้ ในเรื่อง
Storing Hierarchical Data in a Database
ก็เลยได้เปิดหูเปิดตา ว่ามันมี technique อื่นที่ช่วยไม่ให้
การ select หา subtree หรือ path สามารถทำได้ใน select เดียว

ดยเขาจะสร้าง table ให้มี structure แบบนี้

create table foo (
    id long,
    ..
    parent_id long,
    left_id long,
    right_id long
)

ก็คือนอกจากจะมีการเก็บ parent id แล้ว
ก็ยังเก็บค่า left, right ไว้ด้วย
ซึ่งค่านี้ได้จากการ generate โดยการท่อง tree
แบบ Depth-First search

เวลาจะ select หา subtree ก็แค่

select * from foo where left_id between x and y

ค่า x และ y ก็คือ ค่า left_id, right_id ของ node ที่ต้องการหา subtree

...
มีที่น่าสนใจอีกเยอะเลย เช่นจะ select หา path ยังไร,
ผลลัพท์ที่ได้จะสร้างเป็น tree ได้อย่างไร,
การ add note เข้าไปใหม่ จะต้อง update ค่า left, right อย่างไร
ลองไปอ่านดูแล้วกันครับ

Note: อ่านแล้วก็อดนึกถึงคำพูดที่ว่า พวกเด็กที่เรียกไฟฟ้าเขียนโปรแกรมกันทื่อๆ
ก็ถูกของเขาแหล่ะ เพราะเราไม่ได้เรียนมาทาง computer โดยตรง
ก็เลยไม่ได้ผ่านหูผ่านตากับพวก algorithm แบบนี้