login  Naam:   Wachtwoord: 
Registreer je!
 Forum

Beste manier van loopen (Opgelost)

Offline GroundZero - 19/11/2016 10:03
Avatar van GroundZeroLid Hi guys,

eigenlijk een basis vraag maar goed. Wat zou in het volgende geval de beste manier zijn om alle categorieën, subcategorieën en items op te halen?

uitleg: Je hebt hoofdcategorieën. Deze kunnen een subcategorie bevatten maar dit hoeft niet persé. In zowel een hoofdcategorie als een subcategorie kan één of meerdere items zitten. Een snel kort tekstueel voorbeeld:

Hoofdcategorie 1
== Item 1

Hoofdcategorie 2
= Subcategorie 1
== Item 1
== Item 2
= Subcategorie 2

Hoofdcategorie 3

Hoofdcategorie 4
== Item 1
== Item 2
== Item 3



Het lijkt mij dat wanneer je 3 while loops in elkaar doet, dat dit niet de meest efficiënte manier is of wel? Was benieuwd of iemand mij de correcte manier kan vertellen over hoe dit op te halen 

In de database zou alles in één veld kunnen. Het scheiden gebeurd dan door middel van een "type (hoofd/sub/item)" en een "parent ID" veld.

Hoor graag wat jullie kijk hier op is 

5 antwoorden

Gesponsorde links
Offline Thomas - 21/11/2016 13:30 (laatste wijziging 21/11/2016 14:13)
Avatar van Thomas Moderator Er zitten een aantal haken en ogen aan de bovenstaande aanpak.

Allereerst: deze opzet lijkt enkel geschikt voor maximaal drie niveau's diep, maar waarom zou je niet een oplossing maken waarbij er in principe geen begrenzing is in het aantal niveau's?

Op het moment dat men een vierde niveau wil zal er code veranderd/bijgeschreven moeten worden (een vierde loop)?

Bij een generieke opzet hoef je nooit je broncode aan te passen en zou je op andere manieren af kunnen dwingen (denk aan een configuratie-variabele) wat de maximale "diepte" is.

Daarnaast zou bij het uitvoeren van een query in een loop een alarmbel moeten gaan rinkelen: dit is een indicatie dat er ergens iets niet geoptimaliseerd is of dat de aanpak simpelweg onhandig is gekozen. Queries zijn relatief dure operaties. Als je op een makkelijke manier het aantal queries kunt beperken dan zou je deze winst altijd moeten pakken.

Wat je in feite aan het bouwen bent is een boomstructuur. Dit is een structuur waarin elementen aan elkaar gekoppeld zijn via precies één bovengelegen (parent) element. Elk element kan op zijn beurt 0 of meer afstammelingen (children) hebben. Over het bouwen en efficiënt uitlezen van boomstructuren is zeker een heleboel materie te vinden, inclusief implementaties in PHP/MySQL.

Heel bondig samengevat heb je maar één query nodig om de hele boom (of deelboom, gegeven een startpunt) uit te lezen. Vervolgens (her)bouw je deze in PHP middels een data-structuur (dit is niets meer dan een (genest) array).

Hier kun je vervolgens een lineaire lijst (de elementen uit de boom staan in de volgorde waarin je deze af zou drukken) van maken middels een recursieve functie (een functie die zichzelf aanroept) en de eerder opgebouwde data-structuur.

De "truuk" is dus om de elementen in een "voldoende goede" volgorde uit te lezen en deze vervolgens in de data-structuur te zetten. Het rekenwerk voor het "berekenen" van de boom verplaats je dus deels naar PHP. Dit kan in het algemeen een inzetbare strategie zijn: verplaats het probleem deels naar PHP (en probeer niet alles in (My)SQL op te lossen).

Hiertoe dient de data in je database wel een minimale hoeveelheid informatie te bevatten om de boom te kunnen (her)bouwen. Denk hierbij aan:
- element id
- parent element id
- volgorde
(- diepte - niet noodzakelijk, is in principe afleidbaar, maar kan handig zijn)

Mocht je een voorbeeld implementatie willen dan hoor ik het wel, maar hier is echt enorm veel over te vinden op het internet...

EDIT: abstract gezien maak je hier (wederom) gebruik van een "verdeel en heers" strategie waarbij je je programmeerprobleem opdeelt in deelproblemen die je afzonderlijk oplost.
Bedankt door: GroundZero
Offline GroundZero - 21/11/2016 16:34
Avatar van GroundZero Lid Dankjewel voor je antwoord 

Ik heb deze handleiding gevonden, volgens mijn is dit wel een goede aanpak toch? misschien ook handig voor andere mensen.

http://mikehill...a-in-mysql/
Offline Thomas - 22/11/2016 16:26 (laatste wijziging 22/11/2016 17:02)
Avatar van Thomas Moderator Daar worden twee aanpakken beschreven:

- het adjacency list model, en
- het nested set model

In het onderdeel Limitations of the Adjacency List Model worden een aantal beperkingen aangehaald, maar die zijn voornamelijk gestoeld op de aanname dat je enkel een database (en dus enkel SQL) tot je beschikking hebt.

Maar jij bent al bezig in een scriptingtaal waar je de resultaten binnentrekt. In dat onderdeel wordt tevens aangehaald dat de daar genoemde tekortkomingen o.a. via gebruikmaking van "client side code" (deels?) teniet kunnen worden gedaan.

De eerst genoemde oplossing (adjacency list model) kan met wat modificaties (toevoeging van een volgorde-kolom en gebruikmaking van foreign keys) en met wat extra werk aan de PHP-kant van het spectrum prima volstaan.

En je wilt alle informatie ook aan de PHP-kant van het verhaal hebben om de simpele reden dat dat de plek is waar je je boomstructuren nodig hebt en ook daadwerkelijk gebruikt.

Tevens kun je bij de opbouw van je data-structuur deze data ook verrijken, je zou bijvoorbeeld de diepte van een item on-the-fly uit kunnen rekenen. Dit kan dan weer handig in het gebruik zijn in PHP, maar hoeft dus niet opgeslagen te zijn in de database - deze informatie is afleidbaar.

Overigens: In het nested set model ontbreekt een primaire sleutel. Daarnaast zou het ook handig zijn om een index aan te maken op de lft en rgt kolommen.

Uiteindelijk zou je iets moeten kiezen wat handig is in het gebruik. Persoonlijk lijkt mij het nested set model wat minder intuïtief - zelfs als je rechtstreeks in de database kijkt, tenzij je misschien allerlei standaard queries kunt knippen en plakken om informatie over de boomstructuur te visualiseren. Bij het adjacency list model is dat allemaal vele malen makkelijker.

Een goede test om te zien of iets geschikt is is de volgende: wat moet je allemaal doen wanneer er iets verandert, bijvoorbeeld het toevoegen van een item. In de uitgebreide versie van het adjacency list model is dit enkel een kwestie van het vrijmaken van een volgorde-nummer en het opschuiven van de andere elementen. Bij het nested set model houdt dit een hernummering van meestal een aanzienlijk aantal (of percentage) van de items. Indien je boomstructuur (of structuren (meervoud)) vaak veranderen of nogal groot zijn, of beide dan wordt het qua performance misschien toch interessanter om voor een specifieke/andere oplossing te gaan - het gaat er dus ook om hoe je omgaat met de data en hoe vaak deze verandert over tijd.

Zoals eerder gezegd, met de uigebreide versie van het adjacency list model en het bouwen van een data-structuur kan ik volstaan met één query en met een of meer hulpfuncties in PHP kun je een lijst van items uitdraaien die je vervolgens kunt gebruiken om een geneste bulleted list te genereren.

Dit kan ongetwijfeld ook met het nested set model maar daarvoor worden allemaal specifieke queries gebruikt. Daarbij heb je helemaal geen informatie aan de PHP-kant, data zul je elke keer voorgekauwd op moeten halen. Met mijn aanpak trek je deze informatie eenmalig binnen (eenmalig per page-request, anyway ) en heb je vervolgens je complete (en mogelijk verrijkte) boom aan de PHP-kant; daarna heb je op dat moment de database in principe niet meer nodig.
Bedankt door: GroundZero
Offline GroundZero - 24/11/2016 08:59
Avatar van GroundZero Lid Duidelijke uitleg en een goed verhaal, veel lees voer haha. Het is nu duidelijk voor mij, ik zal eens goed na denken over het uiteindelijke resultaat en met oog op de toekomst wat het meest efficiënt is.

Heel erg bedankt voor je uitgebreide antwoorden!
Offline Thomas - 24/11/2016 10:23
Avatar van Thomas Moderator Voorbeeldcode:
  1. <?php
  2. header('Content-Type: text/html; charset=UTF-8');
  3.  
  4. // debug
  5. ini_set('display_errors', 'stdout');
  6.  
  7. // database data
  8. /*
  9. CREATE TABLE mytrees (
  10.   mtr_id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
  11.   mtr_name VARCHAR(255) NOT NULL
  12. ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
  13.  
  14. CREATE TABLE mytree_items (
  15.   mti_id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
  16.   mti_tree_id INT UNSIGNED NOT NULL,
  17.   mti_parent_id INT UNSIGNED,
  18.   mti_order INT UNSIGNED NOT NULL,
  19.   mti_title VARCHAR(255) NOT NULL
  20. ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
  21.  
  22. ALTER TABLE mytree_items ADD FOREIGN KEY (mti_tree_id) REFERENCES mytrees(mtr_id) ON DELETE CASCADE;
  23. ALTER TABLE mytree_items ADD FOREIGN KEY (mti_parent_id) REFERENCES mytree_items(mti_id) ON DELETE CASCADE;
  24.  
  25. INSERT INTO mytrees(mtr_name) VALUES ('test');
  26. SET FOREIGN_KEY_CHECKS = off;
  27. INSERT INTO mytree_items(mti_id, mti_tree_id, mti_parent_id, mti_order, mti_title) VALUES
  28. ( 1, 1, NULL, 1, 'Hoofdcategorie 1'),
  29. ( 2, 1, NULL, 2, 'Hoofdcategorie 2'),
  30. ( 3, 1, NULL, 3, 'Hoofdcategorie 3'),
  31. ( 4, 1, 1, 1, 'Item 1'),
  32. ( 5, 1, 2, 1, 'Subcategorie 1'),
  33. ( 6, 1, 2, 2, 'Subcategorie 2'),
  34. ( 7, 1, 5, 1, 'Item 1'),
  35. ( 8, 1, 5, 2, 'Item 2'),
  36. ( 9, 1, NULL, 4, 'Hoofdcategorie 4'),
  37. (10, 1, 9, 1, 'Item 1'),
  38. (11, 1, 9, 2, 'Item 2'),
  39. (12, 1, 9, 3, 'Item 3');
  40. SET FOREIGN_KEY_CHECKS = on;
  41. */
  42.  
  43. // class definition
  44. class MyTree
  45. {
  46. protected $db;
  47. protected $treeId;
  48. protected $treeData;
  49. protected $treeList;
  50.  
  51. public function __construct($db) {
  52. $this->db = $db;
  53. $this->treeId = false;
  54. $this->treeName = false;
  55. $this->treeData = array();
  56. }
  57.  
  58. public function loadTree($id) {
  59. $this->treeId = false;
  60. $this->treeData = array();
  61.  
  62. $res = $this->db->query(
  63. 'SELECT mtr_name
  64. FROM mytrees
  65. WHERE mtr_id = '.$id
  66. );
  67. if ($res->num_rows == 1) {
  68. $row = $res->fetch_assoc();
  69. $this->treeId = $id;
  70. $this->treeName = $row['mtr_name'];
  71. $this->treeData[0] = array(
  72. // structure data
  73. 'id' => 0,
  74. 'parent' => false,
  75. 'depth' => 0,
  76. 'order' => 1,
  77. 'children' => array(),
  78. // leaf data
  79. 'title' => 'root',
  80. );
  81.  
  82. $res = $this->db->query(
  83. 'SELECT *
  84. FROM mytree_items
  85. WHERE mti_tree_id = '.$this->treeId.'
  86. ORDER BY mti_parent_id, mti_order'
  87. );
  88.  
  89. while ($row = $res->fetch_assoc()) {
  90. $parentId = $row['mti_parent_id'] == NULL ? 0 : $row['mti_parent_id'];
  91. $this->treeData[$row['mti_id']] = array(
  92. 'id' => $row['mti_id'],
  93. 'parent' => $parentId,
  94. 'depth' => ($this->treeData[$parentId]['depth'] + 1),
  95. 'order' => $row['mti_order'],
  96. 'children' => array(),
  97. 'title' => $row['mti_title'],
  98. );
  99. // add item as child of parent
  100. $this->treeData[$parentId]['children'][] = $row['mti_id'];
  101. }
  102. return true;
  103. }
  104. return false; // alternative: throw exception
  105. }
  106.  
  107. public function getData() {
  108. return $this->treeData;
  109. }
  110.  
  111. // create a linear list of the entire current tree, or part of it
  112. protected function makeList($id=0, $reset=true) {
  113. if ($reset) {
  114. $this->treeList = array();
  115. }
  116. // skip root
  117. if ($id > 0) {
  118. $this->treeList[] = $id;
  119. }
  120. foreach ($this->treeData[$id]['children'] as $child) {
  121. $this->makeList($child, false);
  122. }
  123. }
  124.  
  125. // retrieve the list after creating it
  126. public function getList($id=0) {
  127. $this->makeList($id);
  128. return $this->treeList;
  129. }
  130.  
  131. public function printTree($id=0) {
  132. if ($id > 0) {
  133. ?><li><?php
  134. echo escape($this->treeData[$id]['title']);
  135. }
  136. if (count($this->treeData[$id]['children']) > 0) {
  137. ?><ul><?php
  138. foreach ($this->treeData[$id]['children'] as $child) {
  139. $this->printTree($child);
  140. }
  141. ?></ul><?php
  142. }
  143. if ($id > 0) {
  144. ?></li><?php
  145. }
  146. }
  147. }
  148.  
  149. // helper functions
  150. function escape($s) {
  151. return htmlspecialchars($s, ENT_QUOTES, 'UTF-8');
  152. }
  153.  
  154. function dump($a) {
  155. echo '<pre>'.escape(print_r($a, true)).'</pre>';
  156. }
  157. ?>
  158. <!DOCTYPE html>
  159. <html>
  160. <meta charset="UTF-8">
  161. <title>tree</title>
  162. </head>
  163.  
  164. <body>
  165. <?php
  166. $db = new mysqli('host', 'username', 'password', 'database');
  167.  
  168. $tree = new MyTree($db);
  169. if ($tree->loadTree(1)) {
  170. $tree->printTree();
  171. } else {
  172. ?><p>something went wrong :(</p><?php
  173. }
  174. ?>
  175. <body>
  176. </html>


Levert:
  1. <ul>
  2. <li>Hoofdcategorie 1<ul>
  3. <li>Item 1</li>
  4. </ul></li>
  5. <li>Hoofdcategorie 2<ul>
  6. <li>Subcategorie 1<ul>
  7. <li>Item 1</li>
  8. <li>Item 2</li></ul>
  9. </li>
  10. <li>Subcategorie 2</li></ul>
  11. </li>
  12. <li>Hoofdcategorie 3</li>
  13. <li>Hoofdcategorie 4<ul>
  14. <li>Item 1</li>
  15. <li>Item 2</li>
  16. <li>Item 3</li></ul>
  17. </li>
  18. </ul>
Gesponsorde links
Je moet ingelogd zijn om een reactie te kunnen posten.
Actieve forumberichten
© 2002-2024 Sitemasters.be - Regels - Laadtijd: 0.191s