B-Tree ใน Factorio

 (razberry.substack.com)
4 คะแนน โดย GN⁺ 2023-11-17 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • หลังจากอ่านบท B-Tree ในชมรมอ่านหนังสือ Database Internals ผู้เขียนได้นำโครงสร้างข้อมูลไปสร้างขึ้นไม่ใช่ด้วยโค้ด แต่ด้วยโครงสร้างโรงงานใน Factorio เพื่อยืนยันแนวคิดในเชิงภาพ
  • BST จะแยกกิ่งซ้าย·ขวาได้ก็ต่อเมื่อคีย์สามารถเรียงลำดับได้ และหากค่ากระจุกไปด้านใดด้านหนึ่ง ประสิทธิภาพการค้นหาอาจตกลงมาเหลือระดับเดียวกับลิสต์เชิงเส้น
  • สำหรับการจัดเก็บข้อมูลบนดิสก์ ค่าใช้จ่ายในการปรับสมดุลใหม่ ของ BST และการอ่านหลายเพจเป็นภาระ ส่วน B-Tree เป็นโครงสร้างที่ลดปัญหานี้โดยเก็บหลายคีย์ไว้ในโหนดเดียว
  • การสร้างใน Factorio ใช้หีบไม้และแขนกรองสีม่วงแทนโหนดกับการเปรียบเทียบ กำหนดลำดับการเรียงของไอเท็มขึ้นเองเพื่อสร้างเส้นทางค้นหา
  • เวอร์ชัน B-Tree ใช้ 3 คีย์และ 4 พอยน์เตอร์ ต่อโหนด ทำให้ใน 2 ระดับเก็บคีย์ได้มากกว่า BST อย่างมาก แต่ยังเหลือปัญหาเรื่องการแทนค่าและการเรียงลำดับด้วยมือ

ความแตกต่างระหว่าง BST และ B-Tree

  • Binary Search Tree (BST) คือแต่ละโหนดเก็บคีย์หนึ่งตัว คีย์ที่ต่ำกว่าจะถูกส่งไปยังโหนดซ้าย และคีย์ที่สูงกว่าจะถูกส่งไปยังโหนดขวา
    • ตัวอย่างเริ่มจากคีย์ราก 8, ซ้าย 3, ขวา 10
    • ทำงานได้เฉพาะกับ ค่าที่เรียงลำดับได้ ซึ่งสามารถเปรียบเทียบได้ว่าค่าสูงหรือต่ำ
  • หากมีการเพิ่มค่าไปด้านใดด้านหนึ่งมากเกินไป สมดุลของ BST จะเสีย
    • ในกรณีแย่ที่สุด จะเกือบเหมือน ลิสต์เรียงลำดับเชิงเส้น เช่น 8 -> 10 -> 14
    • สามารถแก้ความไม่สมดุลได้โดยใช้ 10 เป็น pivot วางไว้เป็นราก แล้วจัด 8, 14 ไว้สองฝั่ง
  • สำหรับการจัดเก็บข้อมูลบนดิสก์ BST เสียเปรียบ
    • หากต้องคอยรักษาสมดุลใหม่อย่างต่อเนื่อง จะต้องอัปเดตดิสก์และพอยน์เตอร์บ่อยครั้ง
    • โหนดข้างเคียงอาจถูกเก็บอยู่คนละเพจ ทำให้การค้นหาเพียงครั้งเดียวอาจต้องอ่านหลายเพจ
  • B-Tree เก็บหลายคีย์ไว้ในโหนดเดียว และใช้พอยน์เตอร์จำนวน จำนวนคีย์ + 1 ชี้ไปยังโหนดลูก
    • โหนดตัวอย่าง [17 | 24] จะแยกไปยังโหนดลูกสามกลุ่ม ได้แก่คีย์ที่น้อยกว่า 17, คีย์ที่อยู่ระหว่าง 17 กับ 24, และคีย์ที่มากกว่า 24

ต้นไม้ค้นหาที่สร้างไว้ใน Factorio

  • Factorio เป็น เกมสร้างโรงงาน และในการสร้างนี้ แต่ละโหนดของต้นไม้ถูกแทนด้วยโครงสร้างในเกม
  • เริ่มจากการสร้าง BST แบบง่ายก่อน
    • แต่ละโหนดมี หีบไม้ ที่เก็บคีย์หนึ่งตัว และมีสองเส้นทางที่เชื่อมไปยังโหนดอื่น
    • เนื่องจากไม่มีวิธีเปรียบเทียบพื้นฐานระหว่างวัตถุดิบ จึงกำหนดเกณฑ์การเรียงลำดับขึ้นเองเป็น wood, coal, stone, brick, copper, iron, steel
    • แขนกรองสีม่วงทำหน้าที่ตรวจสอบการเปรียบเทียบ
      • ที่โหนดแรก แขนหนึ่งตรวจว่าไอเท็มเท่ากับ brick หรือไม่
      • แขนที่สองตรวจว่าน้อยกว่า brick หรือไม่ เช่น wood, coal, stone
      • แขนที่สามกรองค่าที่มากกว่า เช่น copper, iron, steel
    • ด้านขวาบนยังมี garbage collector สำหรับนำไอเท็มที่เข้ามาผิดบนสายพานลำเลียงออกไปด้วย
  • การสร้าง B-Tree ต้องใช้โครงสร้างมากขึ้นในหนึ่งโหนด
    • แต่ละโหนดมี 3 คีย์, แขนกรอง 3 อัน, หีบไม้ 3 ใบ และพอยน์เตอร์ไปยังลูก 4 ตัว
    • สามารถบรรจุข้อมูลได้มากขึ้นที่ความลึกเท่ากัน
    • ใน 2 ระดับ BST เก็บได้ 2 คีย์ แต่ B-Tree เก็บได้ 12 คีย์
    • ใน 3 ระดับ B-Tree เพิ่มขึ้นได้ถึง 48 คีย์
  • เนื่องจากไม่อยากเลือกและเรียงไอเท็ม 48 ชิ้นใน Factorio ด้วยมือ จึงปล่อย B-Tree ว่างไว้จนกว่าจะหาวิธีแทนค่าที่ดีกว่าได้
  • มีการเปรียบเทียบ BST กับ B-Tree แบบวางข้างกัน และมีวิดีโอ YouTube ประกอบด้วย

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

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

 
GN⁺ 2023-11-17
ความคิดเห็นใน Hacker News

  • เป็นการออกแบบที่ไม่มีประสิทธิภาพนัก แต่การนำ ทฤษฎีวิทยาการคอมพิวเตอร์ มาใช้ใน Factorio ก็ย่อมหมายถึงการเล่นในแบบที่ไม่ใช่วิธีที่เหมาะสมที่สุดอยู่แล้ว
    Factorio ไม่ได้ถูกสร้างมาเพื่อให้เอา B-Tree มาอวด และท้ายที่สุดเครื่องมือต่าง ๆ ก็ถูกออกแบบมาให้เล่น Factorio นั่นเอง

    1. แก่นของ ต้นไม้ปรับสมดุลตัวเอง อย่าง 2-3 tree, red-black tree และ B-Tree ไม่ได้อยู่ที่โครงสร้างต้นไม้เดี่ยว ๆ แต่อยู่ที่ส่วนที่มันปรับสมดุลตัวเองได้ แต่ใน Factorio ไม่สามารถทำให้ต้นไม้จัดโครงสร้างตัวเองใหม่ได้ จึงขาดคุณลักษณะที่สำคัญที่สุดไป
    2. ในมุมมองการปรับให้เหมาะสม inserter ช้ากว่า belt แม้ใช้ inserter 4 ตัวต่อ belt หนึ่งเส้น ก็ย้ายของได้เพียงประมาณ 12 ชิ้นต่อวินาที ขณะที่ blue belt ผลักของได้ 45 ชิ้นต่อวินาที ถ้าเป็นการออกแบบที่เหมาะสมที่สุดโดยใช้เฉพาะ belt ก็ควรใช้ splitter ที่ทำงานได้ 45 ชิ้นต่อวินาที
    3. ดังนั้นจุดที่ splitter กับวิทยาการคอมพิวเตอร์มาบรรจบกันคือ splitter ของ Factorio กับ Benes network ถ้าจะศึกษาเครือข่ายที่สร้างจาก crossbar 2 อินพุต 2 เอาต์พุตล้วน ๆ ให้เริ่มจาก https://en.wikipedia.org/wiki/Clos_network ได้เลย Benes network ก็เป็นเพียง Clos network ขนาด 2 อินพุต 2 เอาต์พุต และ Clos network ก็ทำขนาดตามใจอย่าง 5 ต่อ 7 ได้ด้วย
      เมตาที่น่าค้นหาใน Factorio น่าจะเป็นการออกแบบ “mixed belt”
    • รูปแบบที่เจาะจงกว่านั้นคือ sushi belt ซึ่งเป็น belt เส้นเดียวที่บรรทุกวัตถุดิบหลายชนิดอย่างสมดุลแล้ววนกลับมาหาตัวเอง
      บางแบบแค่รับไอเท็มใหม่เข้ามาตามอัตราส่วนที่กำหนด บางแบบเมื่อเสียสมดุลแล้วก็ปรับกลับให้สมดุลจริง ๆ ด้วย โดยส่วนตัวแล้วชอบอันนี้ที่สุด: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      ตัวอย่างนี้ใช้ตรรกะวงจรในเกม แต่ในฟอรัม Factorio ก็มีหมวดที่ไม่ใช้วงจรด้วย: https://forums.factorio.com/viewforum.php?f=202
      สิ่งที่น่าสนใจคืออ็อบเจกต์ “fish” ใน Factorio เป็นไอเท็มมุกตลกที่ไม่มีประโยชน์ และเพราะมันไม่ได้ถูกใช้ที่ไหน บางครั้งจึงถูกใช้เป็นค่า null, แฟล็กบอกว่า belt วิ่งครบหนึ่งรอบแล้ว หรือเครื่องมือดีบัก: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • คงน่าสนใจถ้ามี ส่วนขยาย Factorio อย่าง “Scriptorio” ที่ทำให้วาง JSON บน conveyor belt ได้ พร้อมกับใช้โรงงานฟังก์ชัน JavaScript หรือ Lua ไปด้วย
      แบบนั้นไม่ใช่แค่อ็อบเจกต์ที่จะ insert/search เท่านั้น แต่ตัว B-Tree เองก็สามารถย้ายไปมาด้วย conveyor belt และ inserter ได้
      อาจเขียนฟังก์ชันค้นหาแบบ recursive ด้วยลูป conveyor belt ที่วิ่งผ่านโรงงาน โดยค่อย ๆ แกะต้นไม้ออกทีละระดับจนถึง leaf แล้วตัดลูปเพื่อส่งผลลัพธ์ออกมาได้
      นี่เป็นโมเดลการรันที่น่าสนใจซึ่งใกล้กับ data flow มากกว่า JavaScript มาตรฐาน ควรอนุญาตให้ conveyor belt, inserter และโรงงานต่าง ๆ ชี้ไปยังอ็อบเจกต์ JSON พื้นฐานเดียวกันด้วยหลาย reference เพื่อให้เกิด “quantum tunneling” หรือ “action at a distance” ไหม? มันอาจมีประโยชน์ แต่ตามธรรมเนียม Factorio ถือว่าไอเท็มทางกายภาพแต่ละชิ้นมีอัตลักษณ์เฉพาะตัว ดังนั้นการไม่รองรับหลาย reference อาจจะ “สมจริง” กว่า หรือไม่ก็อาจให้วิจัยเทคโนโลยี “Quantum Tunneling JSON” ก่อน แล้วอนุญาตให้สร้างหลาย reference ได้เฉพาะใน “JSON Reference Entangler Factory” เท่านั้น
    • ลองอ่านคร่าว ๆ เกี่ยวกับ Clos network แล้ว ถ้าสร้างเครือข่ายแบบนั้นใน Factorio ได้ ก็ดูเหมือนจะทำ การออกแบบ neural network แบบง่าย ๆ อย่างที่เห็นตรงนี้ได้ด้วย: [1]
      น่าจะเป็นไปได้ที่จะปรับเอาต์พุตด้วยการให้น้ำหนักกับความหนาแน่นของทรัพยากรที่ไปถึงตำแหน่งหนึ่ง เมื่อดูจากกลไกตรงนี้ [2] ก็น่าจะใช้การรวม·แยก และความเร็ว belt สามระดับ เพื่อสร้างการตัดสินใจแบบถ่วงน้ำหนักด้วยความหนาแน่นได้
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • ครั้งหน้าอยากเห็นว่าจะทำได้ถึงขั้น ปรับสมดุลตัวเอง ไหม คิดว่า bot น่าจะมีประโยชน์ตรงนี้ แต่ไม่แน่ใจว่าสามารถทำให้ bot สร้าง blueprint แบบไดนามิกได้หรือเปล่า
    • เพราะแบบนี้เลยไม่เล่น Factorio ทรัพยากรสมอง ระดับนั้นเอาไปใช้เพื่อมนุษยชาติได้ และถ้าเอาผลงานมาโชว์ก็ยังได้กระแสตอบรับบนโซเชียลมีเดียด้วย
      เกมที่เรียกร้องสมองเพื่อแลกกับตัวเลขบนหน้าจออยู่ท้ายสุดในลิสต์ของฉัน ฉันอยากเรียนรู้อะไรใหม่ ๆ
      มันอาจมีองค์ประกอบแบบปริศนา และเราก็อาจกำหนดว่ามันสนุกได้ แต่การเรียนก็น่าจะกำหนดให้สนุกได้เหมือนกันไม่ใช่หรือ

  • งานเจ๋งมาก
    มีคนบอกว่ากำลังอ่าน “Database Internals” ในบุ๊กคลับ และสัปดาห์นี้เป็นบทที่ 2 ว่าด้วย B-Tree
    หมายเหตุ แม้ปิดรับสมัครแล้ว แต่ถ้าต้องการก็หา Database Internals มาอ่าน แล้วตามตารางและโน้ตที่นี่แบบ “อ่านอย่างเดียว” ไปด้วยได้: https://eatonphil.com/2023-database-internals.html

  • เหตุผลที่ว่า “binary search tree ไม่เหมาะกับสตอเรจบนดิสก์” นั้นใช้ได้กับ สตอเรจในหน่วยความจำ ด้วย
    การค้นหาในโหนด B-Tree หนึ่งโหนดมักเร็วกว่าการไล่ตามพอยน์เตอร์จำนวนเท่ากันใน binary tree แน่นอนว่าความซับซ้อนในการ implement จะสูงขึ้น แต่ถ้าไม่ได้เขียน C โดยปกติก็คงไม่ลงมือ implement map แบบ tree-based เองอยู่แล้ว
    ยังดัดแปลงได้ด้วย เช่น ใส่รายการใน internal node ให้มากขึ้น แล้วเก็บค่าไว้เฉพาะที่ leaf เท่านั้น ถ้าไม่ได้ทำแค่ set แต่ทำ map ด้วยน่ะนะ ถ้าเชื่อมไปถึงโหนดข้างเคียงด้วย ก็แทบจะใกล้เคียงกับ skip list แล้ว

  • ไม่รู้ทำไมต้องมี คอนเทนต์ Factorio โผล่มาตรงนี้ ทำให้อยากกลับไปจมกับมันอีกสัก 100 ชั่วโมง ปีนี้ก็มีเกมดี ๆ ที่น่าเล่นเยอะเกินพออยู่แล้ว

    • ช่วงปลายปีหน้าน่าจะมีการปรับสมดุลครั้งใหญ่กับ ภาคเสริม Space Age รอถึงตอนนั้นก็อาจไม่เลว

  • ทั้งหมดนี้น่าจะทำได้ด้วย splitter และดูเหมือนไม่จำเป็นต้องใช้หีบหรือ filter inserter คำอธิบายดีนะ

    • ไม่รู้ว่าต้องทำยังไง
      มันไม่ใช่แค่การแยกเอาต์พุตออกเป็นหลายสาย หีบในที่นี้แทนไอเท็มที่เก็บอยู่ใน “โหนด” นั้นของ B-Tree ที่จัดวางแบบสองมิติ
      ยังไม่มีเวลาดูวิดีโอ แต่จากบทความและภาพหน้าจอ ดูเหมือนว่าตรรกะที่เกี่ยวข้องจะอยู่กับ inserter เพื่อรักษาคุณสมบัติ “เรียงลำดับ” ของ tree โดยส่งไอเท็มไปตามเส้นทางของโหนดลูกที่เหมาะสม
      ดูจากการเลือกค่า key ในต้นฉบับ การแยกด้วย splitter ก็น่าจะทำได้ แต่เท่าที่จำได้ splitter รับ filter ได้แค่อย่างเดียว ดังนั้นแต่ละจุดแตกแขนงต้องใช้หลายตัว หมายความว่าต้องใช้เท่ากับจำนวนไอเท็มของจุดแตกแขนงนั้น ส่วน filter inserter อนุญาตให้มีหลาย filter ได้ จึงเหมาะกว่าในกรณีนี้ และก็เห็นได้ในภาพหน้าจอแรกด้วย
      แน่นอนว่าจะเลิกใช้ดีไซน์ B-Tree ทั้งหมด แล้วใช้ splitter n ตัวเพื่อจัดเรียงลงหีบ n ใบก็ได้ แต่นั่นไม่สนุก และดูไม่ใช่สิ่งที่ต้นฉบับตั้งใจ
    • กำลังกำหนด หลายไอเท็ม ให้กับ inserter แต่ละตัว
      filter ของ splitter จะส่งไอเท็มชนิดเดียวไปด้านหนึ่ง และส่งที่เหลือไปอีกด้าน แต่ตัวอย่างนี้ต่างออกไป เพราะมีหลายชนิดไปด้านหนึ่ง และหลายชนิดไปอีกด้าน
    • ต้องเรียงและกรองไอเท็มหลายชนิด เช่น ที่โหนดแรกต้องส่งไม้ ถ่านหิน และหินไปทางซ้าย แล้วส่งโลหะไปทางขวา แต่ filter ของ splitter กรองได้เพียงไอเท็มเดียว

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

    • ก่อนลองเล่นผมก็เคยค่อนข้างกังขาและกังวลแบบเดียวกัน แต่รู้ตัวอีกทีก็ทุ่มไปแล้ว มากกว่า 100 ชั่วโมง
    • ผู้เล่น Factorio ที่ผมรู้จักทุกคนทุ่มไป มากกว่า 1,000 ชั่วโมง กันทั้งนั้น

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

  • นึกว่าจะ implement ด้วย ระบบวงจร ของ Factorio