โพสต์ใหม่จาก Joy Murakami ฉันเคยอ่านบทความนี้มาก่อนแล้ว และมีการอธิบายค่อนข้างชัดเจน
เราจะประสบปัญหานี้ในหลายที่ เช่น การจำแนกประเภทผลิตภัณฑ์ ฟอรัมที่มีโครงสร้างแบบต้นไม้หลายระดับ รายชื่อผู้รับจดหมาย ฯลฯ จะจัดเก็บข้อมูลที่มีโครงสร้างหลายระดับได้อย่างไร
ในแอปพลิเคชัน PHP พื้นที่จัดเก็บข้อมูลแบ็กเอนด์มักจะเป็นฐานข้อมูลเชิงสัมพันธ์ ซึ่งสามารถบันทึกข้อมูลจำนวนมาก และให้บริการเรียกค้นและอัปเดตข้อมูลที่มีประสิทธิภาพ อย่างไรก็ตาม รูปแบบพื้นฐานของข้อมูลเชิงสัมพันธ์คือตารางแบบกากบาท ซึ่งเป็นโครงสร้างแบบเรียบ หากคุณต้องการจัดเก็บโครงสร้างแบบต้นไม้หลายระดับในฐานข้อมูลเชิงสัมพันธ์ คุณต้องดำเนินการแปลที่สมเหตุสมผล ต่อไป ฉันจะพูดคุยกับคุณถึงสิ่งที่ฉันได้เห็นและได้ยินและประสบการณ์เชิงปฏิบัติบางอย่าง
โดยทั่วไปมีวิธีการออกแบบทั่วไปสองวิธีสำหรับการจัดเก็บข้อมูลแบบลำดับชั้นในฐานข้อมูลแบบเรียบ:
รูปแบบรายการที่อยู่ติดกัน
แก้ไขอัลกอริธึมการแวะเวียนต้นไม้แบบสั่งจองล่วงหน้า
ฉันไม่ใช่วิชาเอกคอมพิวเตอร์ และฉันไม่ได้เรียนรู้อะไรเกี่ยวกับโครงสร้างข้อมูลเลย ดังนั้นฉันจึงแปลชื่อทั้งสองนี้ตามตัวอักษร โปรดแจ้งให้เราทราบหากฉันผิด
สองสิ่งนี้อาจฟังดูน่ากลัว แต่จริงๆ แล้วเข้าใจง่ายมาก ที่นี่ฉันใช้ไดเรกทอรีอาหารอย่างง่ายเป็นข้อมูลตัวอย่างของเรา โครงสร้างข้อมูลของเราเป็นดังนี้:
อาหาร
-
|---ผลไม้
-
|. |---แดง
-
|. |--เชอร์รี่
-
|. |---เหลือง
-
|. |--กล้วย
-
|---เนื้อ
-
|--เนื้อวัว
-
|--หมู
เพื่อดูแลผู้ที่ชื่นชอบ PHP ผู้ที่มีปัญหาเรื่อง English
Food: Food
ผลไม้: ผลไม้
สีแดง: สีแดง
เชอร์รี่:เชอร์รี่
สีเหลือง:สีเหลือง
กล้วย:กล้วย
เนื้อ: เนื้อ
เนื้อ:เนื้อวัว
Pork: Pork
adjacency list model
เป็นโมเดลที่เรามักใช้และได้รับการแนะนำในบทช่วยสอนและหนังสือหลายเล่ม เราอธิบายโครงสร้างต้นไม้ทั้งหมดผ่านตารางเรียบโดยการเพิ่มแอตทริบิวต์พาเรนต์ให้กับแต่ละโหนดเพื่อแสดงโหนดพาเรนต์ของโหนดนี้ ตามหลักการนี้ ข้อมูลในตัวอย่างสามารถแปลงเป็นตารางได้ดังนี้:
+--------------------------------------+
|.ผู้ปกครอง |.ชื่อ |
-
|. |. อาหาร |
|. อาหาร |. ผลไม้ |
|. ผลไม้ |. สีเขียว |
|. กรีน |. ลูกแพร์ |
|. ผลไม้ |. สีแดง |
|. แดง |. เชอร์รี่ |
|. ผลไม้ |. เหลือง |
|. เหลือง |. กล้วย |
|. อาหาร |. เนื้อสัตว์ |
|. เนื้อ |. เนื้อ |
|. เนื้อ |. หมู |
-
เราจะเห็นว่า Pear เป็นโหนดลูกของ Green และ Green เป็นโหนดลูกของ Fruit โหนดรูท 'อาหาร' ไม่มีโหนดหลัก เพื่ออธิบายปัญหานี้อย่างง่ายๆ จะใช้เฉพาะชื่อเพื่อแสดงถึงเรกคอร์ดในตัวอย่างนี้ ในฐานข้อมูลจริง คุณต้องใช้ ID ตัวเลขเพื่อระบุแต่ละโหนด โครงสร้างตารางฐานข้อมูลควรมีลักษณะดังนี้: id, parent_id, ชื่อ, คำอธิบาย ด้วยตารางดังกล่าว เราสามารถบันทึกโครงสร้างต้นไม้หลายระดับทั้งหมดผ่านฐานข้อมูลได้
การแสดงแผนผังหลายระดับ หากเราต้องการแสดงโครงสร้างหลายระดับ เราจำเป็นต้องมีฟังก์ชันแบบเรียกซ้ำ
<?php
// $parent คือผู้ปกครองของเด็กที่เราอยากพบ
// $ระดับจะเพิ่มขึ้นเมื่อเราเจาะลึกเข้าไปในต้นไม้
// ใช้เพื่อแสดงฟังก์ชันต้นไม้เยื้องที่ดี
display_children($parent, $level)
-
// รับโหนดลูกทั้งหมดของโหนดพาเรนต์ $parent
$result = mysql_query('เลือกชื่อจากแผนผัง'.
'WHERE parent="'.$parent.'";');
// แสดงแต่ละโหนดย่อย
ในขณะที่ ($row = mysql_fetch_array($result))
-
//เยื้องชื่อโหนด
echo str_repeat(' ',$level).$row['name']"n";
//เรียกใช้ฟังก์ชันนี้อีกครั้งเพื่อแสดงโหนดย่อยของโหนดย่อย
display_children($row['name'], $level+ 1);
-
-
-
การใช้ฟังก์ชันนี้บนโหนดราก (อาหาร) ของโครงสร้างทั้งหมดสามารถพิมพ์โครงสร้างต้นไม้หลายระดับทั้งหมดได้ เนื่องจากอาหารเป็นโหนดรากและโหนดแม่ว่างเปล่า ให้โทร: display_children('',0) จะแสดงเนื้อหาของต้นไม้ทั้งหมด:
อาหาร
ผลไม้
สีแดง
เชอร์รี่
สีเหลือง
กล้วย
เนื้อ
เนื้อวัว
เนื้อหมู
หากคุณต้องการแสดงเพียงส่วนหนึ่งของโครงสร้างทั้งหมด เช่น ส่วนผลไม้ คุณสามารถเรียกมันได้ดังนี้:
display_children('Fruit',0);
เกือบจะใช้วิธีเดียวกันนี้ เราก็สามารถรู้เส้นทางจากโหนดรากได้ ไปยังโหนดใดก็ได้ ตัวอย่างเช่น เส้นทางของเชอร์รี่คือ "อาหาร > ผลไม้ > สีแดง" เพื่อให้ได้เส้นทางดังกล่าว เราต้องเริ่มจากระดับที่ลึกที่สุด "Cherry" ค้นหาเพื่อรับโหนดหลักของมัน "Red" และเพิ่มลงในเส้นทาง จากนั้นเราจะสอบถามโหนดหลักของ Red และเพิ่มลงในเส้นทาง และต่อไปเรื่อยๆ จนถึงระดับบนสุด "อาหาร"
<?php
// $node เป็นโหนดที่ลึกที่สุด
ฟังก์ชั่น get_path($โหนด)
-
// สอบถามโหนดหลักของโหนดนี้
$result = mysql_query('เลือกพาเรนต์จากทรี'.
'WHERE name="'.$node.'";');
$row = mysql_fetch_array($result);
// ใช้อาร์เรย์เพื่อบันทึกเส้นทาง
$path = array();
// หากไม่ใช่โหนดรูท ให้ทำการสืบค้นต่อไป
// (โหนดรูทไม่มีโหนดพาเรนต์)
ถ้า ($แถว['ผู้ปกครอง']!='')
-
// ส่วนสุดท้ายของเส้นทางไปยัง $node คือชื่อ
// ของพาเรนต์ของ $node
$path[] = $row['parent'];
// เราควรเพิ่มพาธไปยังพาเรนต์ของโหนดนี้
//ไปยังเส้นทาง
$path = array_merge(get_path($row['parent']), $path);
}
// คืนเส้นทาง
กลับเส้นทาง $;
-
-
หากคุณใช้ฟังก์ชันนี้สำหรับ "Cherry": print_r(get_path('Cherry')) คุณจะได้รับอาร์เรย์ดังนี้:
อาร์เรย์
-
[0] => อาหาร
[1] => ผลไม้
[2] => สีแดง
-
วิธีการพิมพ์ในรูปแบบที่คุณต้องการนั้นขึ้นอยู่กับคุณ
ข้อเสีย: วิธีนี้ง่ายมาก เข้าใจง่าย และใช้งานง่าย แต่มีข้อเสียอยู่บ้าง สาเหตุหลักมาจากความเร็วในการทำงานช้ามาก เนื่องจากแต่ละโหนดต้องการการสืบค้นฐานข้อมูล และเมื่อปริมาณข้อมูลมีขนาดใหญ่ การสืบค้นจำนวนมากจึงจำเป็นต้องทำให้แผนผังสมบูรณ์ นอกจากนี้ เนื่องจากความจำเป็นในการดำเนินการแบบเรียกซ้ำ การเรียกซ้ำแต่ละระดับจึงจำเป็นต้องใช้หน่วยความจำบางส่วน ดังนั้นประสิทธิภาพการใช้พื้นที่จึงค่อนข้างต่ำ
ตอนนี้เรามาดูวิธีอื่นที่ไม่ใช้การคำนวณแบบเรียกซ้ำและเร็วกว่า นี่คืออัลกอริธึมการแวะผ่านต้นไม้แบบพรีออร์เดอร์ที่แก้ไขแล้ว คุณอาจมีโอกาสสัมผัสวิธีนี้น้อยลง และจะไม่เหมือนกับวิธีข้างต้นเมื่อคุณใช้มัน ครั้งแรก วิธีนี้เข้าใจง่าย แต่เนื่องจากวิธีนี้ไม่ได้ใช้อัลกอริธึมการสืบค้นแบบเรียกซ้ำ จึงมีประสิทธิภาพการสืบค้นที่สูงกว่า
ขั้นแรกเราวาดข้อมูลหลายระดับลงบนกระดาษด้วยวิธีต่อไปนี้ เขียน 1 ทางด้านซ้ายของโหนดราก Food จากนั้นเดินต่อไปตามต้นไม้ เขียน 2 ทางด้านซ้ายของ Fruit จากนั้นจึงเคลื่อนที่ต่อไปตามต้นไม้ทั้งหมด . Edges ติดป้ายกำกับแต่ละโหนดด้วยตัวเลขทางซ้ายและขวา ตัวเลขสุดท้ายคือ 18 ทางด้านขวาของอาหาร ในภาพด้านล่าง คุณจะเห็นโครงสร้างหลายระดับทั้งหมดที่ทำเครื่องหมายด้วยตัวเลข (ไม่เข้าใจเหรอชี้นิ้วไปที่ตัวเลขแล้วนับ 1 ถึง 18 แล้วจะเข้าใจ ถ้ายังไม่เข้าใจให้นับใหม่แล้วระวังขยับนิ้ว)
ตัวเลขเหล่านี้บ่งบอกถึงความสัมพันธ์ระหว่างแต่ละโหนด ตัวเลขของ "สีแดง" คือ 3 และ 6 ซึ่งเป็นโหนดลูกหลานของ "อาหาร" 1-18 ในทำนองเดียวกัน เราจะเห็นว่าโหนดทั้งหมดที่มีค่าด้านซ้ายมากกว่า 2 และค่าด้านขวาน้อยกว่า 11 นั้นเป็นโหนดย่อยของ "Fruit" 2-11
1 อาหาร 18
-
-
-
2 ผลไม้ 11 12 เนื้อ 17
-
-
-
3 สีแดง 6 7 สีเหลือง 10 13 เนื้อ 14 15 หมู 16
-
4 เชอร์รี่ 5 8 กล้วย 9
ด้วยวิธีนี้ โครงสร้างต้นไม้ทั้งหมดสามารถจัดเก็บไว้ในฐานข้อมูลผ่านค่าด้านซ้ายและขวา ก่อนดำเนินการต่อ เรามาดูตารางข้อมูลที่รวบรวมไว้ด้านล่างกันก่อน
-
|.ผู้ปกครอง |.ชื่อ |.lft |
-
|. |. อาหาร |. 1 |. 18
|. อาหาร |. ผลไม้ |. 2 |
|. ผลไม้ |. แดง |. 3 |
|. แดง |. เชอร์รี่ |. 4 |
|. ผลไม้ |. เหลือง |. 7 |
|. เหลือง |. กล้วย |. 8 |
|. อาหาร |. เนื้อสัตว์ |. 12 |
|. เนื้อ |. เนื้อ |. 13 |
|. เนื้อ |. หมู |. 15 |
-
หมายเหตุ: เนื่องจาก "left" และ "right" มีความหมายพิเศษใน SQL เราจึงจำเป็นต้องใช้ "lft" และ "rgt" เพื่อแสดงช่องซ้ายและขวา นอกจากนี้ ฟิลด์ "พาเรนต์" ไม่จำเป็นอีกต่อไปในโครงสร้างนี้เพื่อแสดงโครงสร้างแบบต้นไม้อีกต่อไป กล่าวอีกนัยหนึ่ง โครงสร้างตารางต่อไปนี้ก็เพียงพอแล้ว
-
|.ชื่อ |.lft |
-
|. อาหาร |.1 |. 18 |
|. ผลไม้ |. 2 |. 11 |
|. แดง |.3 |. 6 |
|. เชอร์รี่ |. 4 |. 5 |
|. เหลือง |. 7 |. 10 |
|. กล้วย |. 8 |. 9 |
|. เนื้อ |. 12 |. 17 |
|. เนื้อ |. 13 |. 14 |
|. หมู |. 15 |. 16 |
-
โอเค ตอนนี้เราสามารถรับข้อมูลจากฐานข้อมูลได้แล้ว ตัวอย่างเช่น หากเราต้องการรับโหนดทั้งหมดภายใต้รายการ "Fruit" เราสามารถเขียนคำสั่งแบบสอบถามได้ดังนี้: SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; This แบบสอบถามได้รับผลลัพธ์ดังต่อไปนี้
-
|.ชื่อ |.lft |
-
|. ผลไม้ |. 2 |. 11 |
|. แดง |.3 |. 6 |
|. เชอร์รี่ |. 4 |. 5 |
|. เหลือง |. 7 |. 10 |
|. กล้วย |. 8 |. 9 |
-
ดูสิ คุณสามารถรับโหนดเหล่านี้ทั้งหมดได้ด้วยการสืบค้นเพียงครั้งเดียว เพื่อให้สามารถแสดงโครงสร้างต้นไม้ทั้งหมดเหมือนกับฟังก์ชันแบบเรียกซ้ำข้างต้น เรายังจำเป็นต้องเรียงลำดับแบบสอบถามดังกล่าวด้วย จัดเรียงตามค่า lvalue ของโหนด:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
คำถามที่เหลือคือจะแสดงการเยื้องแบบลำดับชั้นได้อย่างไร
<?php
ฟังก์ชั่น display_tree($root)
-
//รับค่าซ้ายและขวาของโหนดรูท
$result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
$row = mysql_fetch_array($result);
// เตรียมสแต็กค่า r ว่าง
$right = array();
// รับโหนดสืบทอดทั้งหมดของจุดรูท
$result = mysql_query('เลือกชื่อ, lft, rgt จากแผนผัง'
'อยู่ที่ไหนระหว่าง '.$row['lft'].'
$row['rgt'].' ORDER BY lft ASC;');
// แสดงแต่ละแถว
ในขณะที่ ($row = mysql_fetch_array($result))
-
// ตรวจสอบสแต็กหากมีเท่านั้น
ถ้า (นับ($ขวา)>0)
-
// ตรวจสอบว่าเราควรย้ายโหนดออกจากสแต็กหรือไม่
ในขณะที่ ($right[count($right)-1]<$row['rgt'])
-
array_pop($ขวา);
-
}
// เยื้องชื่อของโหนด
echo str_repeat(' ',count($right)).$row['name']"n";
// เพิ่มโหนดนี้ลงในสแต็ก
$right[] = $แถว['rgt'];
-
-
-
หากคุณเรียกใช้ฟังก์ชันข้างต้น คุณจะได้รับผลลัพธ์เช่นเดียวกับฟังก์ชันแบบเรียกซ้ำ เพียงแต่ฟังก์ชั่นใหม่ของเราอาจจะเร็วขึ้นเพราะว่ามีเพียง 2 ฐานข้อมูลคิวรีเท่านั้น มันง่ายกว่าที่จะรู้เส้นทางของโหนด หากเราต้องการทราบเส้นทางของเชอร์รี่เราจะใช้ค่าซ้ายและขวา 4 และ 5 เพื่อสร้างแบบสอบถาม
เลือกชื่อจากแผนผัง โดยที่ lft < 4 และ rgt > 5 เรียงลำดับตาม lft ASC;
สิ่งนี้จะให้ผลลัพธ์ต่อไปนี้:
++----------------+
|.ชื่อ |
-
|. อาหาร |
|. ผลไม้ |
|. แดง |
-
แล้วโหนดหนึ่งๆ มีโหนดลูกหลานกี่โหนด? ง่ายมาก จำนวนลูกหลานทั้งหมด = (ค่า rvalue - ค่าซ้าย - 1)/ลูกหลาน 2 คน = (ขวา - ซ้าย - 1) / 2 ไม่เชื่อเหรอ? ทำคณิตศาสตร์ด้วยตัวเอง เมื่อใช้สูตรง่ายๆ นี้ เราสามารถคำนวณได้อย่างรวดเร็วว่าโหนด "ผลไม้ 2-11" มีโหนดสืบทอด 4 โหนด ในขณะที่โหนด "Banana 8-9" ไม่มีโหนดสืบทอด ซึ่งหมายความว่าโหนดนั้นไม่ใช่โหนดหลัก
น่าทึ่งใช่มั้ย? แม้ว่าฉันจะใช้วิธีนี้มาหลายครั้งแล้ว แต่ก็ยังรู้สึกน่าทึ่งทุกครั้งที่ทำ
นี่เป็นวิธีการที่ดีจริงๆ แต่มีวิธีใดบ้างที่จะช่วยเราสร้างตารางข้อมูลที่มีค่าซ้ายและขวาได้ นี่เป็นอีกฟังก์ชันหนึ่งที่จะแนะนำให้คุณรู้จัก ฟังก์ชันนี้สามารถแปลงตารางที่มีชื่อและโครงสร้างพาเรนต์เป็นตารางข้อมูลที่มีค่าซ้ายและขวาได้โดยอัตโนมัติ
<?php
ฟังก์ชั่น rebuild_tree($parent, $left) {
// ค่าที่ถูกต้องของโหนดนี้คือค่าทางซ้าย + 1
$right = $left+1;
// รับข้อมูลย่อยทั้งหมดของโหนดนี้
$result = mysql_query('เลือกชื่อจากแผนผัง'.
'WHERE parent="'.$parent.'";');
ในขณะที่ ($row = mysql_fetch_array($result)) {
// การดำเนินการแบบเรียกซ้ำของฟังก์ชันนี้สำหรับแต่ละฟังก์ชัน
// ลูกของโหนดนี้
// $right คือค่าขวาปัจจุบัน ซึ่งก็คือ
// เพิ่มขึ้นด้วยฟังก์ชัน rebuild_tree
$right = rebuild_tree($row['name'], $right);
}
// เราได้ค่าด้านซ้าย และตอนนี้เราได้ดำเนินการแล้ว
// ลูกของโหนดนี้เราก็รู้ค่าที่ถูกต้องเช่นกัน
mysql_query('อัปเดตแผนผัง SET lft='.$left.', rgt='
$right.' WHERE name="'.$parent.'";');
// ส่งคืนค่าที่ถูกต้องของโหนดนี้ + 1
กลับ $ขวา+1;
-
-
แน่นอนว่าฟังก์ชันนี้เป็นฟังก์ชันแบบเรียกซ้ำ เราจำเป็นต้องรันฟังก์ชันนี้จากโหนดรูทเพื่อสร้างแผนผังใหม่โดยมีค่าซ้ายและขวา
rebuild_tree('Food',1);
ฟังก์ชันนี้ดูซับซ้อนเล็กน้อย แต่ฟังก์ชันจะเหมือนกับการกำหนดหมายเลขตารางด้วยตนเอง ซึ่งก็คือการแปลงโครงสร้างหลายชั้นสามมิติให้เป็นตารางข้อมูลที่มีค่าด้านซ้ายและขวา
แล้วเราจะเพิ่ม อัพเดต และลบโหนดสำหรับโครงสร้างดังกล่าวได้อย่างไร? โดยทั่วไปมีสองวิธีในการเพิ่มโหนด:
คงชื่อเดิมและโครงสร้างพาเรนต์ ใช้วิธีการเก่าในการเพิ่มข้อมูลลงในข้อมูล และใช้ฟังก์ชัน rebuild_tree เพื่อกำหนดหมายเลขโครงสร้างใหม่ทั้งหมดหลังจากเพิ่มข้อมูลแต่ละชิ้นแล้ว
วิธีการที่มีประสิทธิภาพมากขึ้นคือการเปลี่ยนค่าทั้งหมดทางด้านขวาของโหนดใหม่ ตัวอย่างเช่น: เราต้องการเพิ่มผลไม้ใหม่ "สตรอเบอร์รี่" ซึ่งจะกลายเป็นโหนดลูกสุดท้ายของโหนด "สีแดง" ก่อนอื่นเราต้องสร้างพื้นที่ให้กับมันก่อน ค่าที่ถูกต้องของ "สีแดง" ควรเปลี่ยนจาก 6 เป็น 8 และค่าซ้ายและขวาของ "สีเหลือง 7-10" ควรเปลี่ยนเป็น 9-12 จากการเปรียบเทียบ เราสามารถรู้ได้ว่าถ้าคุณต้องการเพิ่มพื้นที่สำหรับค่าใหม่ คุณต้องเพิ่ม 2 ให้กับโหนดทั้งหมดที่มีค่าซ้ายและขวามากกว่า 5 (5 คือค่าที่ถูกต้องของโหนดย่อยสุดท้ายของ "สีแดง" ). ดังนั้นเราจึงดำเนินการฐานข้อมูลดังนี้:
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
อัปเดตแผนผัง SET lft=lft+2 โดยที่ lft>5;
นี่เป็นการเพิ่มพื้นที่ว่างสำหรับค่าที่แทรกใหม่ ตอนนี้คุณสามารถสร้างโหนดข้อมูลใหม่ในพื้นที่ว่างได้ ค่าซ้ายและขวาคือ 6 และ 7 ตามลำดับ
INSERT INTO tree SET lft=6, rgt=7, name = 'สตรอว์เบอร์รี่'
ลองทำแบบสอบถามอื่นดูสิ! แล้วไงล่ะ? เร็วๆ นี้.
โอเค ตอนนี้คุณสามารถออกแบบโครงสร้างฐานข้อมูลหลายระดับได้สองวิธีที่แตกต่างกัน ขึ้นอยู่กับวิจารณญาณส่วนตัวของคุณ แต่สำหรับโครงสร้างที่มีหลายระดับและจำนวนมาก ฉันชอบวิธีที่สองมากกว่า วิธีแรกจะง่ายกว่าหากปริมาณการสืบค้นมีน้อย แต่จำเป็นต้องเพิ่มและอัปเดตข้อมูลบ่อยๆ
นอกจากนี้ หากฐานข้อมูลรองรับ คุณยังสามารถเขียน rebuild_tree() และการดำเนินการเพิ่มพื้นที่ว่างเป็นฟังก์ชันทริกเกอร์ที่ฝั่งฐานข้อมูล และดำเนินการโดยอัตโนมัติในระหว่างการแทรกและอัปเดต ซึ่งจะทำให้ได้รับประสิทธิภาพการทำงานที่ดีขึ้น และคุณก็สามารถทำได้ เพิ่มโหนดใหม่คำสั่ง SQL จะง่ายขึ้น
วิธีการเรียกซ้ำคลาส
โพสต์โดยแขกเมื่อ 31 พฤษภาคม 2547 - 9:18 น.
ฉันเขียนโปรแกรมโดยใช้วิธี quasi-recursive ซึ่งไม่เหมือนกับการเรียกซ้ำในบทความทุกประการ และฉันกำลังเตรียมที่จะย้ายมันเป็น xoops:
http://dev.xoops.org/modules/xfmod/project/?ulink
ประสบปัญหาหน่วยความจำล้น แต่ฉันวางแผนที่จะใช้วิธีเรียกซ้ำต่อไป ฉันแค่ต้องปรับปรุงต่อไป
ฉันหวังว่าจะมีโอกาสพูดคุย ซม.กับคุณ
» ตอบกลับความคิดเห็นนี้
หรือการเปรียบเทียบทั้งสองวิธี?
โพสต์โดยแขกเมื่อ 17 มีนาคม 2547 - 20:30 น.
ฉันศึกษาบทความนี้อย่างรอบคอบและรู้สึกว่ามันมีประโยชน์มาก แต่แล้วฉันก็คิดอีกครั้งและรู้สึกว่ามีปัญหา (เพื่อประโยชน์ของหน่วยความจำ ฉันเรียกโหมดไดเร็กทอรีที่อยู่ติดกันว่าเป็นวิธีการเรียกซ้ำ และการสำรวจเส้นทางล่วงหน้า อัลกอริทึมแบบต้นไม้ที่ฉันเรียกวิธีการเรียงลำดับต้นไม้ล่วงหน้า):
1. ความแตกต่างที่ใหญ่ที่สุดระหว่างสองวิธีคือการเรียกซ้ำต้องใช้สแต็กเมื่อทำการสืบค้น ในขณะที่การเรียงลำดับต้นไม้ล่วงหน้าต้องใช้ครึ่งหนึ่งของโหนด (อ้างอิงถึงครึ่งหลังของ โหนดที่แทรก) เมื่ออัพเดตโหนดของการอัพเดต แม้ว่าคุณจะบอกด้วยว่าหากมีโหนดจำนวนมากและการอัปเดตบ่อยครั้ง ประสิทธิภาพของแผนผังที่เรียงลำดับไว้ล่วงหน้าจะลดลง และการเรียกซ้ำจะดีกว่า หากมีระดับโหนดหลายระดับ ก่อนอื่นเลย การเรียกซ้ำจะทำให้เกิดสแต็กโอเวอร์โฟลว์ และ นอกจากนี้การเรียกซ้ำเองก็ไม่ได้มีประสิทธิภาพมากนัก อีกทั้งการเรียกซ้ำแต่ละระดับยังต้องใช้งานฐานข้อมูลอีกด้วย ผลโดยรวมจะไม่เหมาะนัก แนวทางปัจจุบันของฉันคือการดึงข้อมูลทั้งหมดในครั้งเดียว จากนั้นดำเนินการแบบเรียกซ้ำบนอาเรย์ ซึ่งจะดีกว่า หากสามารถปรับปรุงเพิ่มเติมได้ คุณสามารถเพิ่มโหนดรูทลงในแต่ละแถวของเรคคอร์ดได้ (ปัจจุบันเท่านั้น) โหนดพาเรนต์ที่อยู่ติดกันจะถูกบันทึกไว้) เพื่อให้ประสิทธิภาพในการค้นหาต้นไม้สาขาสูงขึ้นและจะสะดวกมากในการอัพเดตต้นไม้ซึ่งน่าจะเป็นวิธีที่ดีกว่า
2. ปรับปรุงวิธีการเรียกซ้ำ ในบทความ เมื่อคำนวณค่าด้านซ้ายและด้านขวาของโหนดต้นไม้ที่เรียงลำดับไว้ล่วงหน้า จริงๆ แล้วจะใช้วิธีสำรวจผ่านสแต็ก ถูกนำไปใช้ด้วยตนเอง หากอ้างอิงวิธีนี้ในอัลกอริธึมแบบเรียกซ้ำ หากคุณใช้อาร์เรย์แทนสแต็กเมื่อดำเนินการเรียกซ้ำ คุณยังสามารถปรับปรุงประสิทธิภาพของการเรียกซ้ำได้
3. การเห็นพ้องต้องกัน หากคำนึงถึงความพร้อมกันโดยเฉพาะอย่างยิ่งเมื่ออัปเดตแผนผัง วิธีการอัปเดตข้อมูลโหนดในพื้นที่ขนาดใหญ่ของแผนผังที่เรียงลำดับไว้ล่วงหน้าจำเป็นต้องให้ความสนใจเป็นพิเศษกับการใช้กลไกการล็อคและการทำธุรกรรมเพื่อให้มั่นใจ ความสอดคล้องของข้อมูล
4. ในกรณีของโหนดรูตหลายโหนดหรือโหนดพาเรนต์หลายโหนด ในกรณีนี้ เห็นได้ชัดว่าไม่ใช่แผนผังไบนารี่มาตรฐานหรือแผนผังหลายทางแยก อัลกอริทึมของต้นไม้ที่เรียงลำดับไว้ล่วงหน้าจำเป็นต้องได้รับการปรับปรุงอย่างมากเพื่อปรับตัว และวิธีการเรียกซ้ำ ถูกนำไปใช้อย่างอิสระ ดังนั้นในกรณีนี้ การเรียกซ้ำจึงสามารถปรับเปลี่ยนได้มากขึ้น แน่นอน เนื่องจากวิธีการเรียกซ้ำเป็นรูปแบบหนึ่งของรายการที่เชื่อมโยง สามารถแสดงต้นไม้และกราฟด้วยรายการที่เชื่อมโยง และแน่นอนว่าสามารถปรับเปลี่ยนได้สูง
5. ใช้งานง่าย หากคุณสังเกตข้อมูลที่จัดเก็บไว้ในฐานข้อมูลโดยตรงโดยไม่มีการทำงานของโปรแกรม จะเห็นได้ชัดว่าข้อมูลที่จัดเก็บในโหมดเรียกซ้ำนั้นใช้งานง่ายกว่า ในขณะที่ข้อมูลในแผนผังที่เรียงลำดับไว้ล่วงหน้านั้นอ่านได้ยากโดยตรง (สำหรับลำดับชั้น ความสัมพันธ์) นี่เป็นสิ่งสำคัญในการแลกเปลี่ยนข้อมูลหรือไม่
โดยทั่วไปแล้ว โดยส่วนตัวแล้วฉันชอบใช้วิธีการเรียกซ้ำ แต่ฉันกังวลอยู่เสมอเกี่ยวกับผลกระทบของการเรียกซ้ำต่อประสิทธิภาพ โชคดีที่ฉันไม่ได้สัมผัสกับระดับการจำแนกประเภทขนาดใหญ่ การใช้อาร์เรย์แทนการใช้สแต็กแบบเรียกซ้ำจะเป็นการปรับปรุงที่ดีกว่า วิธี. ต้นไม้ที่เรียงลำดับไว้ล่วงหน้าเป็นวิธีที่มีประสิทธิภาพในการแก้ต้นไม้แบบง่าย ๆ เมื่อคุณคุ้นเคยกับมันแล้ว มันควรจะดีมาก โดยเฉพาะการค้นหาแบบย้อนกลับจากโหนดใบไปยังโหนดรูทนั้นสะดวกมาก
หมาป่า
www.fwolf.com
» ตอบกลับความคิดเห็นนี้
มีความสุขมากที่ได้เห็นคำตอบของคุณ
โพสโดย shuke เมื่อ 18 มีนาคม 2547 - 05:47 น.
ฉันดีใจมากที่คุณอ่านบทความนี้อย่างละเอียด บทความนี้เผยแพร่ครั้งแรกบน sitepoint.com โดยหวังว่าจะแนะนำวิธีการบางอย่างให้กับเพื่อน ๆ ที่ต้องการเริ่มต้น วิธีการของคุณก็ดีมากเช่นกัน ฉันจะลองดูถ้ามีโอกาส (หากคุณสนใจ ทำไมไม่เขียนวิธีการและโค้ดการใช้งานเฉพาะของคุณเป็นบทช่วยสอนตามตัวอย่างข้างต้น เพื่อให้ทุกคนสามารถเลียนแบบได้ด้วยตัวอย่างที่เป็นประโยชน์มากขึ้น) หากคุณมีคำถามเกี่ยวกับการบันทึกโครงสร้างหลายระดับในฐานข้อมูล หากคุณ มีความสนใจในการวิจัย ต่อไปนี้เป็นลิงก์ที่ดีอีกสองลิงก์ที่สามารถใช้เป็นข้อมูลอ้างอิงได้:
ขอแนะนำสี่วิธีทั่วไปของการสืบค้นครั้งเดียวและสคริปต์การเรียงลำดับอาร์เรย์ ฉันคิดว่าสคริปต์ของคุณต้องดีกว่านี้
นอกจากนี้ ฉันเห็นว่าคุณยังใช้ drupal อีกด้วย นอกจากนี้ยังมีฟีเจอร์ขั้นสูงที่เรียกว่าระบบการตรวจสอบสิทธิ์ผู้ใช้แบบกระจาย ตราบใดที่คุณลงทะเบียนบนไซต์ drupal ใดก็ตาม คุณสามารถเข้าสู่ระบบเพื่อเข้าถึงไซต์ drupal อื่น ๆ ได้ ค่อนข้างน่าสนใจ
ด้วยความปรารถนาดี!
» ตอบกลับความคิดเห็นนี้
การสร้างต้นไม้โดยใช้ลูปได้ถูกนำมาใช้แล้ว
โพสต์โดยแขกเมื่อ 25 มีนาคม 2547 - 22:10 น.
ฉันได้อ่านข้อมูลทั้งหมดที่คุณให้ไว้เมื่อครั้งที่แล้ว แต่ตามจริงแล้ว ไม่มีอะไรใหม่มากนักในบทความแรก บางทีฉันอาจไม่เข้าใจมันดีนัก บทความที่สองเขียนด้วย PHP3 และโครงสร้างของโปรแกรม ไม่มีรายละเอียด ดูสิ มีการใช้ฟังก์ชันทางแยกมากเกินไป
มันเกิดขึ้นจนฉันจำเป็นต้องใช้บทบาทผู้ใช้แบบมีลำดับชั้นในระบบ ดังนั้นฉันจึงเขียนการข้ามผ่านตามแนวคิดของอาร์เรย์ ฉันไม่มีเวลาจัดเรียงมัน ดังนั้นฉันจะใส่มันไว้ที่นี่ เพื่อให้คุณพิจารณา ฐานข้อมูลคือ ADODB และโปรแกรมถูกแยกออกจากระบบโดยตรง ฉันหวังว่าจะสามารถอธิบายได้อย่างชัดเจน โดยหลักแล้วจะใช้การดำเนินการอาเรย์อันทรงพลังของ PHP และใช้ลูปเพื่อดำเนินการเรียกซ้ำ ความคิดเห็นเป็นวิธีการที่คล้ายกัน แต่ระยะเวลาในการประมวลผลผลลัพธ์จะแตกต่างกัน
<?php
-
* แสดงรายการ
* @เข้าถึงสาธารณะ
-
ฟังก์ชัน DispList()
-
//โหมดการแสดงผลที่ไม่มีการเยื้อง
// $this->mIsDispListIndex = true;
// echo('<p align="right"><a href="?action=new&part=role">เพิ่มบทบาทใหม่</a> </p>'); _fcksavedurl=""?action=new&part=role ">เพิ่มบทบาทใหม่</a> </p>');"
-
// $this->mListTitle = 'รายการบทบาทผู้ใช้';
// $this->SetDataOption('list');
-
// $this->SetQueryTable( array($this->mTableUserRole) );
-
// //สอบถามสั่งซื้อ
// $this->SetQueryOrder( 'asc', $this->mTableUserRole, 'sequence' );
-
// $this->Query('list');
// parent::DispList();
// //วิธีการแสดงผลอื่นโดยใช้อาร์เรย์เป็นสแต็ก A: บันทึกบทบาทเมื่อกดบนสแต็กและลบแหล่งที่มาหลังจากกด
// $this->CheckProperty('mrDb');
// $this->CheckProperty('mrSql');
// $this->mrSql->Select('role, title, parent');
// $this->mrSql->จาก($this->mTableUserRole);
// $this->mrSql->Orderby('parent, sequence');
// $this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
// ถ้า (0 < นับ($this->mRs))
-
// $source = & $this->mRs->GetArray(); // ดัชนีตัวเลข
// $stack = array(''); //stack
// $stacki = array(-1); //สอดคล้องกับสแต็ก บันทึกระดับของข้อมูลในสแต็กในแผนผัง
// $target = array();
// ในขณะที่ (0 < นับ($stack))
-
// $item = array_shift($stack);
// $lev = array_shift($stacki);
// ถ้า (!ว่าง($รายการ))
-
// //ใส่ข้อมูลที่ประมวลผลแล้วลงในอาร์เรย์เป้าหมายที่นี่
// array_push($target, str_repeat(' ', $lev) . $item);
// //$s1 = str_repeat(' ', $lev) .
-
// $del = array(); //โหนดที่จะลบออกจาก $source
// $ar = array(); // โหนดที่ต้องเพิ่มในสแต็ก
// foreach ($แหล่งที่มาเป็น $key=>$val)
-
// // ค้นหาโหนดย่อยที่ตรงกัน
// ถ้า (ว่าง ($รายการ))
-
// $find = Empty($source[$key]['parent']);
-
//อื่น
-
// $find = ($item == $source[$key]['parent']);
-
// ถ้า ($ ค้นหา)
-
// array_unshift($ar, $source[$key]['role']);
// $del[] = $คีย์;
-
-
// foreach ($ar เป็น $val)
-
//array_unshift($สแต็ค, $val);
//array_unshift($stacki, $lev + 1);
-
// foreach ($del เป็น $val)
-
// unset($source[$val]);
-
// echo(implode(', ', $stack) . '<br />' . implode(', ', $stacki) . '<br />' . implode(', ', $target) . '< br /><br />');
-
//debug_array();
-
//อื่น
-
// echo('<center>ไม่มีการดึงข้อมูล</center>');
// }
//วิธีการแสดงผลอื่นโดยใช้อาร์เรย์เป็นสแต็ก B: บันทึกดัชนีอาร์เรย์เมื่อกดสแต็ก นำออกจากสแต็กแล้วลบแหล่งที่มาหลังการใช้งาน
$this->CheckProperty('mrDb');
$this->CheckProperty('mrSql');
$this->mrSql->Select('role, title, parent');
$this->mrSql->จาก($this->mTableUserRole);
$this->mrSql->Orderby('parent,ลำดับ');
$this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
ถ้า (!empty($this->mRs) && !$this->mRs->EOF)
-
$source = & $this->mRs->GetArray(); // ดัชนีตัวเลข
$stack = array(-1); //stack
$stacki = array(-1); //สอดคล้องกับสแต็ก บันทึกระดับของข้อมูลในสแต็กในแผนผัง
$เป้าหมาย = อาร์เรย์();
ในขณะที่ (0 < นับ($สแต็ค))
-
$item = array_shift($สแต็ค);
$lev = array_shift($stacki);
ถ้า (-1 != $รายการ)
-
//ใส่ข้อมูลที่ประมวลผลแล้วลงในอาร์เรย์เป้าหมายที่นี่
$s1 = str_repeat(' ', $lev) '<a href="?action=disp&part=role&role=' . $source[$item]['role'] . '">' . ['ชื่อ'] '</a>';
$s2 = '<a href="?action=edit&part=role&role=' . $source[$item]['role'] . '">แก้ไข</a> <a href="?action=delete&part=role&role= ' . $source[$item]['role'] '">ลบ</a>';
array_push($เป้าหมาย, อาร์เรย์($s1, $s2));
-
$del = array(); //โหนดที่จะลบออกจาก $source
$ar = array(); //โหนดที่ต้องเพิ่มในสแต็ก
foreach ($แหล่งที่มาเป็น $key=>$val)
-
// ค้นหาโหนดย่อยที่ตรงกัน
ถ้า (-1 == $รายการ)
-
$find = Empty($source[$key]['parent']);
-
อื่น
-
$find = ($source[$item]['role'] == $source[$key]['parent']);
-
ถ้า($ ค้นหา)
-
array_unshift($ar, $key);
-
-
foreach ($ar เป็น $val)
-
array_unshift($สแต็ค, $val);
array_unshift($stacki, $lev + 1);
-
//ลบออกจากแหล่งที่มา
ไม่ได้ตั้งค่า($แหล่งที่มา[$รายการ]);
//echo(implode(', ', $stack) . '<br />' . implode(', ', $stacki) . '<br />' . implode(', ', $target) . '< br /><br />');
-
//เอาท์พุท
echo('<p align="right"><a href="?action=new&part=role">เพิ่มบทบาทใหม่</a> </p>');
array_unshift($target, array('บทบาท', 'การดำเนินการ'));
$this->CheckProperty('mrLt');
$this->mrLt->SetData($เป้าหมาย);
$this->mrLt->mListTitle = 'รายการบทบาทผู้ใช้';
$this->mrLt->mIsDispIndex = false;
$นี่->mrLt->Disp();
-
อื่น
-
echo('<center>ไม่มีการดึงข้อมูล</center>');
-
} // สิ้นสุดฟังก์ชัน DispList
-