ต้นไม้ปลอม: ใช้การเยื้องเพื่อ UI ที่เรียบง่ายขึ้น

 (ratfactor.com)
4 คะแนน โดย GN⁺ 2024-01-01 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แม้ดูเหมือนว่าต้องใช้ UI แบบลำดับชั้น สิ่งแรกที่ควรตรวจสอบคือข้อมูลจำเป็นต้องมี ความสัมพันธ์แบบพ่อแม่-ลูก จริงหรือไม่ หรือแค่ต้องดูเหมือนเป็นแบบนั้นก็พอ
  • หากไม่จำเป็นต้องมี tree จริง ก็สามารถแสดงโครงสร้างบนหน้าจอได้ด้วยเพียง ลำดับการจัดเรียงแบบสัมบูรณ์ ของรายการทั้งหมดและค่า indent แทนการใช้ ID ของพ่อแม่
  • ตัวแก้ไขเกม Hiss จัดเรียงชื่ออย่าง banana.eat แล้วแสดงส่วนหลังจุด (.) ด้วยการเยื้อง ทำให้เกิด UI ที่ดูเหมือน namespace
  • วิธีนี้ใกล้เคียงกับ การแก้ไขแบบโปรแกรมประมวลผลคำ ที่ผู้ใช้ย้ายรายการขึ้นลงและเพิ่ม/ลดการเยื้อง จึงลดภาระจากโครงสร้างข้อมูลแบบ tree
  • หากจำเป็นต้องค้นหาหรือรักษาความสัมพันธ์ระหว่างรายการจริง ๆ ควรใช้ โมเดล tree จริง แทนการแฮ็กด้วยการเยื้องหรือสัญลักษณ์ในสตริง

รายการที่ไม่ใช่ tree แต่ดูเหมือน tree

  • เมื่อในแอปพลิเคชันต้องการแสดงรายการแบบไดนามิกอย่าง Foo, Bar เป็น tree view โดยทั่วไปมักนึกถึงโครงสร้างที่เชื่อมแต่ละรายการเข้ากับรายการพ่อแม่
  • ในฐานข้อมูลเชิงสัมพันธ์ เช่น อาจเก็บ ID ของพ่อแม่ไว้ในคอลัมน์ parent
    • parent ของ Foo คือ null
    • parent ของ Foo 1 คือ Foo
    • parent ของ Foo 1.a คือ Foo 1
  • การดึงข้อมูล tree แบบนี้ด้วย SQL อาจต้องใช้วิธีอย่าง recursive CTE
  • แต่สำหรับรายการจำนวนมาก สิ่งที่สำคัญกว่าความสัมพันธ์จริงอาจเป็น รูปแบบที่จัดไว้ให้อ่านง่าย สำหรับมนุษย์

วิธีเก็บค่าการเยื้องเป็นข้อมูล

  • หากไม่จำเป็นต้องมีความสัมพันธ์พ่อแม่-ลูกจริง สามารถเก็บรายการด้วยฟิลด์ต่อไปนี้เท่านั้น
    • id
    • sort
    • indent
    • name
  • sort ไม่ได้หมายถึงลำดับภายในรายการย่อย แต่หมายถึง ลำดับแบบสัมบูรณ์ของรายการทั้งหมด
  • indent แทนปริมาณพื้นที่ที่จะใส่หน้ารายการโดยตรง ทำให้การเรนเดอร์หน้าจอง่ายขึ้น
  • UI สำหรับแก้ไขก็อาจง่ายกว่าการจัดการ tree
    • ผู้ใช้สามารถย้ายรายการขึ้นลงได้
    • สามารถเพิ่มการเยื้องหรือดึงการเยื้องออกได้
    • หากจำเป็น อาจเพิ่มกฎง่าย ๆ เพื่อบังคับการเยื้องที่ถูกต้อง
  • ผลลัพธ์คือประสบการณ์ใกล้เคียงกับ การแก้ไขรายการในโปรแกรมประมวลผลคำ มากกว่าการจัดการโครงสร้างข้อมูลแบบตำราวิทยาการคอมพิวเตอร์โดยตรง

namespace ปลอมแบบใช้จุด (.) ของ Hiss

  • ตัวแก้ไขเกม text adventure Hiss แสดงชื่ออย่าง banana, banana.eat, banana.peel ใน UI ให้ดูเหมือนเป็นลำดับชั้น
  • ไม่ได้มีการใช้งานฟีเจอร์ namespace จริงใน HissScript
  • วิธีใช้งานนั้นเรียบง่าย
    • จัดเรียงชื่อ object ตามลำดับตัวอักษร
    • หากชื่อมีจุด (.) ให้ตัดส่วนหน้าออก
    • แสดงส่วนที่เหลือโดยเยื้องเข้าไป
  • ลอจิกหลักของโค้ดตัวอย่างก็เป็นไปตามลำดับเดียวกัน
    • จัดเรียง things.keys
    • หากแต่ละชื่อมีจุด ให้เยื้องแล้วลบส่วนก่อนจุดออกก่อนแสดงผล
    • หากไม่มีจุด ให้แสดงชื่อเดิม
  • หลังจากนั้นมีการเพิ่มการตรวจสอบอีกไม่กี่บรรทัดเพื่อดูว่ามีรายการ “พ่อแม่” ที่มีคำนำหน้าตามที่กำหนดอยู่หรือไม่
  • สามารถเพิ่มการซ้อนลึกได้ตามต้องการ แต่ตอนนี้ยังรอจนกว่าจะมีความจำเป็นจริง
  • UI ที่ดูเหมือน namespace นี้สำคัญต่อคนที่จัดระเบียบเกม แต่ไม่มีความหมายพิเศษสำหรับตัวแก้ไขเกมและผู้เล่น
    • ชื่อที่มีจุดก็เป็นเพียงชื่อ
    • ส่วนที่ดูเหมือน namespace มีหน้าที่เพียงช่วยให้ชื่อยังไม่ซ้ำกัน

กรณีคล้าย tree ที่จัดการเป็นรายการแบน

  • Dave Long เสนอวิธีเก็บเส้นทางและข้อมูลไว้ใน รายการแบน ในฐานะ “tree จริงแบบเทคโนโลยีต่ำ”
  • นี่เป็น insight ที่คล้ายกับตัวอย่าง banana.eat
  • ลองนึกถึงรายการเส้นทางในรูปแบบต่อไปนี้ คล้าย output ของ find
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • หากต้องการ traversal แบบ depth-first ก็แค่ จัดเรียงตามลำดับพจนานุกรม ของเส้นทาง
  • หากต้องการ traversal แบบ breadth-first สามารถกลับเส้นทางโดยอิงจากตัวคั่นเส้นทาง เพิ่มรายการว่างเพื่อปรับระดับความลึกให้เท่ากัน แล้วจึงจัดเรียง
  • ตัวอย่างนี้มีไว้เพื่อแสดงแนวคิด ในทางปฏิบัติ วิธีที่เป็นธรรมชาติกว่าคือแยกบรรทัดด้วยตัวคั่นแล้วจัดการเป็น array
  • โดยรวมแล้วรายการแบนจัดการได้ง่าย และหากเป็นไปได้ก็ชอบแนวทางที่ใส่รายการไว้ใน plain old lists

อุปมา scrapbook บนพื้น

  • ในงาน scrapbook ส่วนตัว อาจวางรูปถ่าย โน้ต โปสต์การ์ด ตั๋วต่าง ๆ กระจายบนพื้นแล้วจัดเป็นกลุ่มได้
  • สำหรับมนุษย์ ความสัมพันธ์ของกลุ่มอาจดูชัดเจน แต่พื้นเองไม่มีอุปกรณ์ทางกายภาพที่บังคับความสัมพันธ์นั้น
  • แก่นของอุปมานี้คือ ความสัมพันธ์ที่ถูกแสดงออกมา กับ ความสัมพันธ์เชิงโครงสร้างจริง อาจแตกต่างกันได้
  • รายการใน UI ก็เช่นกัน การจัดวางที่ดูเหมือนลำดับชั้นสำหรับมนุษย์ อาจไม่ได้หมายถึงลำดับชั้นจริงในโมเดลข้อมูลภายใน

กรณีที่จำเป็นต้องใช้ tree จริง

  • วิธีที่อิงกับการเยื้องหรือสัญลักษณ์ในสตริงต้องปรับตามสถานการณ์อย่างมาก และในบริบทการเขียนโปรแกรมทั่วไปมีโอกาสถูกมองว่าเป็น การแฮ็ก
  • หากจำเป็นต้องรู้ความสัมพันธ์ระหว่างรายการจริง ๆ ควรใช้ โครงสร้าง tree จริง ที่เหมาะกับโมเดลข้อมูล เช่น ID ของพ่อแม่ หรือตาราง join แบบพ่อแม่-ลูก
  • หากเป็นสถานการณ์อย่างการจำแนกโปรเจกต์วิจัยขนาดใหญ่ที่ต้องการระดับการจัดระเบียบแบบตู้เอกสารและแฟ้มทางกายภาพ “วิธีบนพื้น” ก็ไม่เหมาะสม
  • ในโปรเจกต์ที่ภายหลังจำเป็นต้องรู้ความสัมพันธ์ระหว่างรายการจริง ๆ หากเลียนแบบโครงสร้างด้วยการเยื้องหรือจำนวนสัญลักษณ์ในสตริง ก็อาจกลายเป็นเส้นทางที่เจ็บปวดตลอดอายุโปรเจกต์และช่วงเวลาบำรุงรักษา

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-01-01
ความคิดเห็นบน Hacker News

  • วิธีแรก หรือก็คือวิธีที่ดูเหมือนว่า “แน่นอนว่าต้องมีแค่วิธีนี้” เรียกว่า adjacency list
    ส่วนวิธีที่สองที่ว่า “ง่ายกว่ามาก” นั้นจำไม่ได้ว่าเคยเห็นมาก่อน และแม้จะมีข้อเสียที่ชัดเจน แต่ในบางกรณีก็ดูเหมือนว่าเพียงพอ
    วิธีที่สามคือการ “ทำเป็นเนมสเปซ” ซึ่งเรียกว่า materialized path และยังมีอีกวิธีในการแทนต้นไม้คือ nested sets: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    สมัยที่ผู้คนยังจัดการฐานข้อมูลเชิงสัมพันธ์กันอย่างจริงจัง เรื่องพวกนี้เป็นความรู้ที่รู้จักกันดีทั้งหมด และก็มีบทความอย่างเช่น http://www.dbazine.com/oracle/or-articles/tropashko4/
    ตอนนี้มันดูเหมือนเป็นความรู้ที่ถูกลืมไปแล้ว

    • หนึ่งในช่วงเวลาที่ฉันเกลียดที่สุดในที่ทำงานเก่าคือ ตอนที่พยายามอย่างหนักเพื่ออธิบายปัญหาหนึ่ง แต่กลับมีคนจำได้ว่ามันเป็น แนวคิดที่มีอยู่แล้ว ซึ่งมีทั้งชื่อเรียกและงานวิจัยรองรับ
      ระหว่างที่กำลังทำความเข้าใจหลายแง่มุมของปัญหาด้วยตัวเอง ฉันรู้สึกว่ามันยากมากที่จะค้นหาชื่อที่ใช้เรียกแนวคิดนั้นอยู่แล้ว
    • จริงเลย ทุกวันนี้บัณฑิตจบใหม่รุ่นเยาว์ที่รับเข้ามามักพยายามยัดทุกอย่างลงใน เอกสาร NoSQL และแทบไม่อยากคิดเรื่องการทำ data modeling เลย
      สุดท้ายก็ไปจัดการตรรกะทั้งหมดสำหรับการแสดงต้นไม้ในโค้ด ทั้งที่ฐานข้อมูลเชิงสัมพันธ์สมัยใหม่ร่วมกับ CTE ไม่กี่ตัวสามารถรองรับกรณีใช้งานจำนวนมากได้อย่างสวยงามแบบแทบไม่ต้องออกแรง
    • จะบอกว่าเป็นความรู้ที่ถูกลืมก็คงไม่ถูกนัก ยังมีหนังสือชื่อ “Joe Celko's Trees and Hierarchies in SQL” อยู่
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • ถ้าสนใจหัวข้อนี้ แนะนำให้เริ่มจากหาหนังสือของ https://en.m.wikipedia.org/wiki/Joe_Celko มาอ่านก่อน

  • ใน Postgres มี ชนิดข้อมูล ltree และตัวดำเนินการค้นหาที่ทำงานแบบเนทีฟในลักษณะนี้: https://www.postgresql.org/docs/current/ltree.html
    ตัวอย่างเช่นใส่ CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy'); แล้ว
    ใช้ SELECT path FROM test WHERE path <@ 'Top.Science'; เพื่อค้นหา Top.Science และ Top.Science.Astronomy ได้

    • ข้อควรระวังสำหรับโปรแกรมเมอร์: ความพิเศษอย่างหนึ่งของ ltree คือ เส้นทางกลางที่ถ้าวาดเป็นต้นไม้แล้วจะเป็นโหนดพ่อแม่ ไม่จำเป็นต้องมีอยู่จริงก็ได้
      ในตัวอย่างข้างบน ต่อให้ลบเรคอร์ด Top.Science ไป เรคอร์ด Top.Science.Astronomy ก็จะไม่ถูกตัดออกไปด้วย
      ป้ายกำกับในค่า ltree บ่งบอกต้นไม้เชิงตรรกะผ่าน materialized path แต่ไม่ได้บังคับให้ต้องมีเรคอร์ดที่ตรงกับโหนดพ่อแม่ทุกตัวที่ถูกบ่งชี้เอาไว้
      ขึ้นอยู่กับแอปพลิเคชัน นี่อาจเป็นพฤติกรรมที่ต้องการพอดี หรืออาจตรงกันข้ามเลยก็ได้ ถ้าเป็นกรณีหลัง ก็จำเป็นต้องมีกลไกเพิ่มเติมเพื่อรักษาความถูกต้องของข้อมูล
    • ถ้าจะเก็บพาธของไฟล์ สงสัยว่าสามารถใช้ / เป็นตัวคั่นได้ไหม
    • สงสัยว่ามีใครมีประสบการณ์ด้านประสิทธิภาพบ้างไหม ดูเหมือนจะมีการประมวลผล regex เยอะพอสมควร
    • ใน SQL Server ก็มีฟีเจอร์ที่คล้ายกันมาก[1] และจากที่เคยใช้มาก็ทำงานได้ค่อนข้างดี
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • สงสัยว่าสามารถทำแบบเดียวกันด้วย คอลัมน์ JSON ได้ไหม แบบนั้นก็จะใช้ชนิดข้อมูลที่ไม่ใช่สตริงกับโหนดได้ด้วย
      แต่ก็มีความกังวลว่าดัชนีของ JSON อาจทำงานได้ไม่ดีเท่าดัชนีของ ltree

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

    • ผู้เขียนก็ระบุไว้ชัดแล้วว่า “คนมักคิดว่าต้องเข้ารหัสความสัมพันธ์พ่อ-ลูกอย่างเป็นทางการเสมอ แต่จริง ๆ แล้วบางครั้งก็ไม่จำเป็น และแค่ต้องการการแสดงผลแบบซ้อนกันก็พอ” ซึ่งการตอบกลับแบบนี้ก็ดูแปลก ๆ
      คำตอบคือ “ไม่ ไม่มีทาง” งั้นหรือ?
      มีเหตุผลที่ YAGNI เป็น heuristic ด้านการออกแบบที่มีชื่อเสียง แนวคิดแบบ “สมมติไว้ก่อนว่าต้องใช้เสมอ” ไม่ถูกต้อง
    • ที่น่าขันคือก็ยังใช้ parent ID อยู่ในข้อมูลเหมือนเดิม
      แค่เอาไปแปะไว้หน้าสตริงข้อมูลแทนที่จะเก็บในคอลัมน์เฉพาะของชนิดข้อมูลที่เหมาะสม
      มันอาจไม่ใช่ตัวเลข หรือไม่ใช่คอลัมน์ ID ก็ได้ แต่ก็ยังเป็นตัวระบุที่ชี้ไปยังค่าที่คาดหวังอีกตัวอยู่ดี ดังนั้นเปลี่ยนรูปแบบก็ไม่ได้ทำให้มันเลิกเป็น parent ID
    • แม้ใช้วิธีเข้ารหัสลำดับ/indentation แบบในต้นฉบับ ก็ควรสร้างความสัมพันธ์พ่อ-ลูกกลับมาได้ไม่ยาก
      แน่นอนว่าต้องรับประกันด้วยว่าจะไม่บันทึก indentation ที่ผิด เช่น มีลูกแต่ไม่มีพ่อ
      เพราะงั้นวิธีที่ง่ายที่สุดน่าจะเป็นเก็บเป็น ลำดับ/ความลึก ก่อน แล้วค่อย migrate ไปเป็นโมเดลพ่อ/ลูกเมื่อถึงเวลาต้องทำฟีเจอร์ที่ต้องใช้
      แต่คำว่า “indentation” ควรนิยามให้เป็นนามธรรมมากขึ้นว่าเป็นความลึกในต้นไม้ ไม่ใช่จำนวนช่องว่างที่จะ render จริง ๆ แบบนี้จะหาข้อมูลผิดพลาดได้ง่ายกว่า migrate ทีหลังก็ง่ายกว่า และยังยืดหยุ่นเรื่องการ render สำหรับผู้ใช้แต่ละคนได้ด้วย ไม่ว่าจะเป็น / ซ้อนกัน, tab, 8 ช่อง, 4 ช่อง, 1 ช่อง ฯลฯ
    • ถ้ามีโครงสร้างข้อมูลอย่าง struct item_t { char key[255]; char display_value[255]; } และ key มี ตัวคั่น path ที่สม่ำเสมออย่าง a/b/c การหาพ่อกับลูกจะง่ายมาก
      แย่ที่สุดก็แค่ไล่เช็กอาร์เรย์แบบเชิงเส้น และถ้ามีการเรียงลำดับอยู่แล้ว ก็ดูแค่รายการก่อนหน้าจนกว่าจะถึงพ่อได้เลย
    • เห็นด้วยมาก denormalization บางครั้งอาจเป็นทางเลือกที่ดีได้ แต่กรณีนี้ผมไม่คิดว่ามีเหตุผลรองรับที่สมเหตุสมผล

  • ผมเคยเริ่มบริษัทที่มีข้อมูลแบบต้นไม้จำนวนมาก การแปลงโครงสร้างต้นไม้เป็น รายการแบบเยื้อง ทำได้ในเวลา O(n)
    ตอนนั้นมันเป็นหนึ่งในคำถามสัมภาษณ์ด้วย และก็มีหลายวิธีในการเก็บข้อมูลในฐานข้อมูล SQL หลายแบบเพื่อดึงบางส่วนของต้นไม้มา render ได้เร็วโดยไม่ต้องใช้ recursive query
    พอเข้าใจแนวคิดพวกนี้แล้ว การเก็บข้อมูลให้เป็นต้นไม้อย่างถูกต้องจะมีข้อดีกว่าวิธี indentation แบบนี้มาก

    • ถ้าไม่ต้องการข้อดีเหล่านั้น มันก็ไม่สำคัญเท่าไร

  • “วิธีหนึ่งในการดึงข้อมูลโครงสร้างต้นไม้จากฐานข้อมูลเชิงสัมพันธ์ด้วย SQL คือใช้ recursive CTE (Common Table Expressions) ซึ่งก็สนุกพอ ๆ กับชื่อของมัน”
    CTE ไม่ได้น่ากลัวเลย แม้จะรวม recursive CTE ด้วย และพอคุ้นแล้วรับรองได้ว่ามันสนุกจริง

    • CTE ไม่ได้สนุกอะไรขนาดนั้น การต้องคัดลอก CTE ทั้งกองไปแปะในหน้าต่าง SQL อื่นเพื่อ debug ส่วนที่สนใจไม่ใช่ความบันเทิงแบบที่ผมมองหา
    • ตอนประกอบข้อมูลต้นไม้จาก representation ที่ normalized นั้น recursive CTE ช้ามาก
      ถ้าจะประกอบ path ของโหนดที่มีความลึก d เวลาที่ใช้กว่าจะได้ผลลัพธ์จาก query ก็ช้าลงอย่างน้อย d เท่า
      ข้อดีคือการแก้ไขต้นไม้มีต้นทุนต่ำ แต่การแก้ไขเกิดขึ้นน้อยกว่าการอ่านมาก
    • CTE ก็โอเคนะ ผู้เขียนอาจทำเป็น view ที่มี ชื่อที่จัดรูปแบบแล้ว ด้วย CTE แทนที่จะ bake ข้อมูลนี้ลงในตารางก็ได้

  • ตรงนี้ทำให้เห็นความต่างระหว่าง HN กับ Reddit ในประเด็นที่ว่า “หลายครั้งคนไม่ได้ต้องการต้นไม้จริง ๆ แค่อยากได้สิ่งที่ดูเหมือนต้นไม้”
    ใน HN คอมเมนต์ลูกจะเป็น nextSibling ของคอมเมนต์พ่อ และทำให้มันดูเหมือนต้นไม้ด้วยการเพิ่มค่า indentation ของพ่ออีก 1
    ส่วน Reddit อย่างน้อยใน old.reddit.com คอมเมนต์ลูกจะถูกซ้อนอยู่ภายในคอมเมนต์พ่อจริง ๆ สำหรับเว็บใหม่ผมไม่แน่ใจ

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

  • แกนหลักของบทความนี้เรียบง่าย คือควรใช้ โครงสร้าง ที่เหมาะกับปัญหา
    แต่ผมคิดว่าการเล่าเรื่องผิดทางไปหน่อย การดึงต้นไม้จากฐานข้อมูลไม่จำเป็นต้องใช้ CTE เสมอไป จะดึงรายการแบบแบนมาแล้วประกอบเป็นต้นไม้ในเครื่องก็ได้ ซึ่งยังไงก็มักต้องทำอยู่แล้วเพื่อเอาไปจัดการต่อ
    ถ้าใช้ตรรกะเดียวกัน เราก็อาจบอกคนที่ใช้ฐานข้อมูลเชิงสัมพันธ์เพื่อเก็บรายการว่าให้เก็บในไฟล์ข้อความไปเลย ทำไมต้องยอมจ่ายค่า network latency?
    ในทางกลับกัน โครงสร้างที่เสนอมากลับทำงานได้ไม่ดีนักถ้าต้นไม้ใหญ่พอและต้องย้ายกิ่งหรือเปลี่ยนความลึก เพราะมันมีต้นทุนเชิงเส้น
    ผู้เขียนควรบอกเจตนาตั้งแต่แรก อธิบายตัวอย่างสามแบบแล้วค่อยมาหักล้างในตอนจบด้วย “ถ้าต้องการต้นไม้ก็ใช้ต้นไม้” แบบนี้ไม่ค่อยดีนัก ถึงอย่างนั้นถ้าเอาประโยคนี้ไว้ตั้งแต่ต้น บทความก็คง clickbait น้อยลงมาก

  • หลายปีก่อนผมมี moment เข้าใจอะไรคล้าย ๆ กันกับ OpenGL ผมไม่ได้จำเป็นต้อง render โลกของวัตถุ 3D แบบลำดับชั้น แต่แค่ render รายการสามเหลี่ยมที่จัดเรียงแล้ว ก็พอ
    ความคิดนี้เหมือนเปิดสวิตช์ในหัว และทำให้ optimization หลายอย่างง่ายขึ้นมาก

    • ใช่เลย ในเกม 3D หลังปี 2000 ความเรียบง่ายทรงพลังมาก
      แม้ในเกมที่มีลำดับชั้นของเอนทิตีซับซ้อน เวลาจะใส่เข้า render queue ก็มักต้อง flatten อยู่ดีด้วยเหตุผลอย่างการ sort ตาม transparency
      “รายการแบบแบนของสิ่งของต่าง ๆ” ก็เป็นรากฐานของ ECS/DOD เช่นกัน

  • มีหนังสือทั้งเล่มที่ว่าด้วยการจัดการเรื่องแบบนี้ในฐานข้อมูล
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • เห็นบอกว่าหนังสือทุกเล่มเหมาะสำหรับมือใหม่ แบบนี้ก็ดีเลย

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

    • จะมองว่าต้นไม้ที่แทนด้วย nested JSON เป็นต้นไม้ที่ “จริง” กว่าต้นไม้เสมือนที่ได้จากการเก็บ parent reference ไว้ในฐานข้อมูลก็ยังได้