{"id":20068,"date":"2024-02-07T07:24:01","date_gmt":"2024-02-07T06:24:01","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=20068"},"modified":"2024-02-13T07:39:19","modified_gmt":"2024-02-13T06:39:19","slug":"exercices-indexation","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/analisis-de-software\/ejercicios-de-indexacion-corregidos\/","title":{"rendered":"2 ejercicios de indexaci\u00f3n corregidos"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"20068\" class=\"elementor elementor-20068\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-036d901 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"036d901\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-41e2b12\" data-id=\"41e2b12\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ce40aea elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ce40aea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/analyse-logicielle\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Analyse Logicielle<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-70c3f07\" data-id=\"70c3f07\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1f64b1c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1f64b1c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-5894097\" data-id=\"5894097\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-adad193 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"adad193\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/UML_(informatique)\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-00340c3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"00340c3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ea5516b\" data-id=\"ea5516b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-758291a elementor-widget elementor-widget-heading\" data-id=\"758291a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Alternar tabla de contenidos\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/analisis-de-software\/ejercicios-de-indexacion-corregidos\/#Exercices-Corriges-Indexation-de-cles-dans-une-base-de-donnees\" >Exercices Corrig\u00e9s - Indexation de cl\u00e9s dans une base de donn\u00e9es<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/analisis-de-software\/ejercicios-de-indexacion-corregidos\/#Exercice-indexation-simple\" >Exercice indexation simple<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/analisis-de-software\/ejercicios-de-indexacion-corregidos\/#Exercice-index-mutliples\" >Exercice index mutliples<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-Corriges-Indexation-de-cles-dans-une-base-de-donnees\"><\/span>Exercices Corrig\u00e9s - Indexation de cl\u00e9s dans une base de donn\u00e9es<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e359af8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e359af8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fa0b0c9\" data-id=\"fa0b0c9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3f4281e elementor-widget elementor-widget-text-editor\" data-id=\"3f4281e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Les index des bases de donn\u00e9es sont trait\u00e9s par indexation afin de trouver au plus vite leur enregistrement dans une base de donn\u00e9es. Voici une s\u00e9rie d&rsquo;exercice traitant ce probl\u00e8me. Le cours sur les arbres binaires de recherche traite aussi ce probl\u00e8me en th\u00e9orie des graphes.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"indexation\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a25198f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a25198f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-367716d\" data-id=\"367716d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-290f686 elementor-widget elementor-widget-heading\" data-id=\"290f686\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-indexation-simple\"><\/span>Exercice indexation simple<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f09192c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f09192c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-03b8949\" data-id=\"03b8949\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-87b5a3d elementor-widget elementor-widget-text-editor\" data-id=\"87b5a3d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Rappelons quelques d\u00e9finitions :<\/p><ol><li>Index = table permettant d\u2019associer \u00e0 une cl\u00e9 d\u2019article (donn\u00e9e d\u2019application) l\u2019adresse relative de cet article (position dans le fichier)<\/li><li>M\u00e9thodes d\u2019acc\u00e8s index\u00e9 = fa\u00e7on d\u2019aller chercher des articles (donn\u00e9es d\u2019application) dans un fichier \u00e0 partir d\u2019organisation index\u00e9e (\u00e8 index primaire)<\/li><li>Densit\u00e9 d\u2019un index = quotient du nombre de cl\u00e9s dans l\u2019index sur le nombre d\u2019articles du fichier. Ainsi, un index dense\u00a0poss\u00e8de autant de cl\u00e9s qu\u2019il y a d\u2019articles dans le fichier. Si le fichier est tri\u00e9, on peut utiliser un index non dense (ex\u00a0: la cl\u00e9 la plus grande des articles de chaque bloc avec l\u2019adresse relative du bloc)<\/li><li>Index hi\u00e9rarchis\u00e9 = index sur un index, sur un index, \u2026 pour acc\u00e9l\u00e9rer la recherche de la cl\u00e9 dans l\u2019index<\/li><li>Index discriminants ou non = sur une donn\u00e9e discriminante ou non (identifiant un article de mani\u00e8re unique ou non)<\/li><li>Index pla\u00e7ant = qui range les articles dans l\u2019ordre des cl\u00e9s et les restitue dans l\u2019ordre en lecture s\u00e9quentielle de la m\u00e9moire<\/li><li>Index primaire = qui est bas\u00e9 sur la cl\u00e9 des articles, permet de les ranger en m\u00e9moire (au passage, acc\u00e9l\u00e8re l\u2019acc\u00e8s sur cl\u00e9)<\/li><li>Index secondaire = un acc\u00e9l\u00e9rateur d\u2019acc\u00e8s, cet index est non-discriminant<\/li><\/ol><p>Les organisations <em>index\u00e9es<\/em> n\u00e9cessitent la cr\u00e9ation d&rsquo;un index tri\u00e9 sur lequel sont appliqu\u00e9es les recherches dichotomiques d&rsquo;une valeur de cl\u00e9 discriminante ou non. Le fichier \u00e9tant lui-m\u00eame tri\u00e9 sur cl\u00e9, l&rsquo;index correspondant est de type primaire non dense. Cet index peut \u00eatre vu comme une table de couples\u00a0 (val_cl\u00e9, adr_page) o\u00f9 val_cl\u00e9 est la plus petite cl\u00e9 des articles stock\u00e9s dans la page r\u00e9f\u00e9renc\u00e9e par adr_page. Lorsque l&rsquo;index est de grande taille, on le d\u00e9compose en une arborescence dont chaque n\u0153ud a une taille inf\u00e9rieure ou \u00e9gale \u00e0 une page. Le n\u0153ud sommet de l&rsquo;arborescence est appel\u00e9 racine de l&rsquo;index.\u00a0<\/p><p>Lors de la recherche d&rsquo;une valeur de cl\u00e9 dans l&rsquo;index, un examen de la racine permet de d\u00e9terminer la partie de l&rsquo;arbre dans laquelle se poursuivra la recherche en renvoyant sur un n\u0153ud de niveau imm\u00e9diatement inf\u00e9rieur. L&rsquo;examen de ce n\u0153ud permet \u00e0 son tour d&rsquo;affiner l&rsquo;intervalle de recherche. Ce processus r\u00e9cursif s&rsquo;applique jusqu&rsquo;\u00e0 rencontrer un n\u0153ud ou une feuille (n\u0153ud de plus bas niveau de l&rsquo;arbre) contenant la valeur de cl\u00e9 cherch\u00e9e et l&rsquo;adresse de la page associ\u00e9e. Les organisations arborescentes se diff\u00e9rencient par le principe suivant lequel est g\u00e9r\u00e9e la dynamicit\u00e9 de l&rsquo;index hi\u00e9rarchique.\u00a0<\/p><p>Ce principe d\u00e9termine les performances obtenues tant au niveau du nombre d&rsquo;E\/S n\u00e9cessaires pour parcourir l&rsquo;index qu&rsquo;au niveau du taux d&rsquo;occupation de chaque n\u0153ud de la hi\u00e9rarchie.<\/p><p>Un <em>arbre balanc\u00e9<\/em> est \u00e9galement appel\u00e9 <em>arbre-B<\/em>, <em>B-tree<\/em> ou <em>arbre \u00e9quilibr\u00e9<\/em>. Intuitivement, il est possible de construire une arborescence dynamique de la fa\u00e7on suivante. Lorsqu&rsquo;un index est de grande taille, il est possible d&rsquo;indexer \u00e0 son tour le fichier contenant cet index et ce, de fa\u00e7on r\u00e9cursive jusqu&rsquo;\u00e0 ce que l&rsquo;index de plus haut niveau (la racine) tienne sur une seule page. Compte tenu de la dynamicit\u00e9 de l&rsquo;index, la racine elle-m\u00eame peut cro\u00eetre et ne plus tenir dans une page.\u00a0<\/p><p>On rajoute alors un niveau \u00e0 la hi\u00e9rarchie d&rsquo;index. La hi\u00e9rarchie grossit donc par la racine de telle sorte que tous les chemins de la racine aux feuilles ont m\u00eame longueur. La d\u00e9finition formelle d&rsquo;un arbre-B est donn\u00e9e ci-dessous et est illustr\u00e9e sur l&rsquo;exemple de la Figure 1.<\/p><p><em>Un arbre-B d&rsquo;ordre m est un arbre tel que<\/em><\/p><p><em>(i)\u00a0\u00a0\u00a0\u00a0 chaque n\u0153ud contient k cl\u00e9s tri\u00e9es, avec m &lt;=<\/em><em>\u00a0k &lt;=<\/em><em>\u00a02m sauf la racine pour laquelle k v\u00e9rifie 1<\/em><em>&lt;= k <\/em><em>&lt;= 2m.<\/em><\/p><p><em>(ii)\u00a0\u00a0\u00a0 tout n\u0153ud non feuille a (k+1) fils. Le i\u00e8me\u00a0fils a des cl\u00e9s comprises les (i-1)\u00e8me\u00a0et i\u00e8me\u00a0cl\u00e9s du p\u00e8re.<\/em><\/p><p><em>(iii)\u00a0\u00a0 l&rsquo;arbre est \u00e9quilibr\u00e9.<\/em><\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-20089 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd47.png\" alt=\"indexation B-tree\" width=\"568\" height=\"198\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd47.png 568w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd47-300x105.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd47-18x6.png 18w\" sizes=\"(max-width: 568px) 100vw, 568px\" \/><\/p><p><strong>Question 1\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Compte tenu de la d\u00e9finition formelle des arbre-B, quelle seront les hauteurs minimale et maximale (nombre de niveaux) d&rsquo;un arbre-B d&rsquo;ordre m contenant n cl\u00e9s ?<\/p><p><strong>Question 2\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Quels sont les crit\u00e8res de choix de l&rsquo;ordre d&rsquo;un arbre-B si l&rsquo;on utilise cette structure pour construire un index ?<\/p><p><strong>Question 3<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Quel est l&rsquo;int\u00e9r\u00eat que la structure d&rsquo;un index arborescent soit \u00e9quilibr\u00e9e ?<\/p><p><strong>Question 4<\/strong><\/p><p>Dans les applications r\u00e9elles, les cl\u00e9s d&rsquo;acc\u00e8s peuvent \u00eatre de taille variable. En d\u00e9duire le format de stockage du n\u0153ud d&rsquo;un arbre-B. Quelle est l&rsquo;utilit\u00e9 des bornes m et 2m fix\u00e9es pour le nombre k de cl\u00e9s par n\u0153ud et comment faut-il interpr\u00e9ter ces bornes dans de cas de cl\u00e9s de taille variable ?<\/p><p><strong>Question 5\u00a0\u00a0\u00a0\u00a0<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/p><p>Repr\u00e9senter l&rsquo;arbre-B de la Figure 1 apr\u00e8s insertion des cl\u00e9s 37 puis 36.<\/p><p><strong>Question 6<\/strong><\/p><p>Repr\u00e9senter l&rsquo;arbre-B de la Figure 1 apr\u00e8s suppression des cl\u00e9s 17 puis 31.<\/p><p><strong>Question 7<\/strong><\/p><p>De nombreuses applications ex\u00e9cutent des traitements s\u00e9quentiels tri\u00e9s sur leurs fichiers. La structure d&rsquo;arbre-B est-elle bien adapt\u00e9e \u00e0 ce type de traitements ? Combien d&rsquo;E\/S n\u00e9cessite un parcours s\u00e9quentiel tri\u00e9 de toutes les cl\u00e9s de l&rsquo;arbre-B pr\u00e9sent\u00e9 Figure 1 ? Proposer une optimisation de cette structure permettant de lire uniquement les feuilles de l&rsquo;arbre lors d&rsquo;un parcours s\u00e9quentiel tri\u00e9. Cette organisation est connue sous le nom arbre-B+. Discuter des avantages des\u00a0 arbres B+ par rapport aux arbres B.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-07dce95 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"07dce95\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-adcccfb\" data-id=\"adcccfb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c0bbaff elementor-widget elementor-widget-toggle\" data-id=\"c0bbaff\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2021\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2021\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2021\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2021\"><p><strong>Question 1<\/strong><\/p><p>La hauteur d&rsquo;un arbre-B \u00e9volue de fa\u00e7on logarithmique par rapport au nombre de cl\u00e9s stock\u00e9es dans l&rsquo;arbre. En effet, dans un arbre-B d&rsquo;ordre m, chaque n\u0153ud poss\u00e8de entre (m+1) et (2m+1) fils. On peut donc stocker, au niveau i+1 de l&rsquo;arbre-B, entre (m+1) et (2m+1) fois plus de cl\u00e9s qu&rsquo;au niveau i, suivant que l&rsquo;arbre est faiblement ou fortement occup\u00e9. Les formules de calcul de la hauteur minimale et maximale d&rsquo;un arbre-B, en fonction de son ordre et du nombre de cl\u00e9s qu&rsquo;il contient, sont donc:<\/p><p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 h_min \u00bb log_(2m+1) n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 h_max \u00bb log_(m+1) n<\/p><p>Par exemple, un arbre-B d&rsquo;ordre 100 peut contenir plus de 8 millions de cl\u00e9s sur seulement trois niveaux.\u00a0<\/p><p><strong>Question 2<\/strong><\/p><p>Lors d&rsquo;une recherche (ou d&rsquo;une \u00e9criture) dans un index, l&rsquo;acc\u00e8s \u00e0 chaque n\u0153ud travers\u00e9 dans l&rsquo;arborescence g\u00e9n\u00e8re une E\/S. Les hauteurs minimale et maximale de l&rsquo;arborescence bornent donc le co\u00fbt en E\/S de recherche d&rsquo;une cl\u00e9 dans l&rsquo;index. Or, il a \u00e9t\u00e9 montr\u00e9 dans la question pr\u00e9c\u00e9dente que plus l&rsquo;ordre de l&rsquo;arbre-B est grand, plus sa hauteur est faible. D&rsquo;autre part, on a montr\u00e9 que le nombre de comparaisons engendr\u00e9es par la recherche d&rsquo;une cl\u00e9 dans un arbre-B est ind\u00e9pendant de l&rsquo;ordre de cet arbre-B.\u00a0<\/p><p>Il est donc int\u00e9ressant de choisir un ordre aussi grand que possible afin de stocker un maximum de cl\u00e9s par n\u0153ud et minimiser la hauteur de l&rsquo;index. Ce choix doit cependant tenir compte de la taille maximale des n\u0153uds d&rsquo;arbre-B. Cette taille est born\u00e9e par la taille d&rsquo;une page disque afin d&rsquo;assurer que la lecture d&rsquo;un n\u0153ud n\u00e9cessite une seule E\/S.\u00a0<\/p><p><strong>Question 3<\/strong><\/p><p>Une arborescence \u00e9quilibr\u00e9e garantit un co\u00fbt d&rsquo;acc\u00e8s constant \u00e0 toute valeur de cl\u00e9 ind\u00e9pendamment de la distribution des cl\u00e9s. Il est donc possible de borner le nombre d&rsquo;E\/S n\u00e9cessaire \u00e0 la recherche ou \u00e0 l&rsquo;\u00e9criture d&rsquo;un article. Cette propri\u00e9t\u00e9 est particuli\u00e8rement importante en bases de donn\u00e9es. En effet, lorsque plusieurs chemins d&rsquo;acc\u00e8s peuvent \u00eatre emprunt\u00e9s pour acc\u00e9der \u00e0 un article, un SGBD doit \u00eatre capable de faire automatiquement le choix optimal.<\/p><p><strong>Question 4<\/strong><\/p><p>Un n\u0153ud d&rsquo;arbre-B contient un ensemble de couples (cl\u00e9, pointeur fils) et un pointeur additionnel r\u00e9f\u00e9ren\u00e7ant le premier n\u0153ud fils (un n\u0153ud contenant n cl\u00e9s poss\u00e8de n+1 fils), comme illustr\u00e9 Figure 1. Si la taille des cl\u00e9s est fixe, cette taille est stock\u00e9e dans le descripteur d&rsquo;index. Si la taille des cl\u00e9s est variable, deux solutions sont envisageables:<\/p><p>\u2013 les cl\u00e9s sont encadr\u00e9es par un caract\u00e8re sp\u00e9cial. Ce caract\u00e8re, appel\u00e9 s\u00e9parateur, doit avoir un codage binaire diff\u00e9rent de tous les octets susceptibles d&rsquo;\u00eatre contenus dans une cl\u00e9. De plus, la lecture de la i\u00e8me\u00a0cl\u00e9 d&rsquo;un n\u0153ud n\u00e9cessite la lecture octet par octet de toutes les cl\u00e9s la pr\u00e9c\u00e9dant dans ce n\u0153ud.<\/p><p>\u2013 les cl\u00e9s sont pr\u00e9c\u00e9d\u00e9es d&rsquo;un champ longueur. Cette technique est la seule applicable si le codage binaire des cl\u00e9s couvre l&rsquo;ensemble des codes binaires possibles. La i\u00e8me\u00a0cl\u00e9 d&rsquo;un n\u0153ud peut ainsi \u00eatre acc\u00e9d\u00e9e en sautant de champ longueur en champ longueur.<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-20090 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd48.png\" alt=\"bdd indexation b-tree\" width=\"518\" height=\"78\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd48.png 518w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd48-300x45.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd48-18x3.png 18w\" sizes=\"(max-width: 518px) 100vw, 518px\" \/><\/p><p><strong>Figure 1.<\/strong> Format de stockage d&rsquo;un noeud d&rsquo;arbre-B<\/p><p>Les bornes m et 2m assurent que le taux de remplissage d&rsquo;un n\u0153ud varie entre 50% et 100% (et est donc en moyenne de 75%). Dans la d\u00e9finition des arbres-B,\u00a0 ce taux de remplissage k est exprim\u00e9 en nombre de cl\u00e9s par n\u0153ud. Lorsque l&rsquo;on utilise des arbres-B contenant des cl\u00e9s de taille variable, le taux de remplissage d&rsquo;un n\u0153ud doit alors \u00eatre exprim\u00e9 en nombre d&rsquo;octets plut\u00f4t qu&rsquo;en nombre de cl\u00e9s.<\/p><p><strong>Question 5<\/strong><\/p><p>Les insertions des cl\u00e9s 37 puis 36 sont illustr\u00e9es sur la Figure. L&rsquo;insertion de la cl\u00e9 36 provoque l&rsquo;\u00e9clatement de la feuille o\u00f9 elle doit \u00eatre ins\u00e9r\u00e9e. La remont\u00e9e de la cl\u00e9 m\u00e9diane 37 provoque \u00e0 son tour l&rsquo;\u00e9clatement du n\u0153ud p\u00e8re de cette feuille. L&rsquo;arbre-B cro\u00eet donc par le haut et reste \u00e9quilibr\u00e9.<em>\u00a0\u00a0 <\/em><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20091 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd49.png\" alt=\"bdd indexation b-tree\" width=\"579\" height=\"198\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd49.png 579w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd49-300x103.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd49-18x6.png 18w\" sizes=\"(max-width: 579px) 100vw, 579px\" \/><\/p><p><strong>Figure 2.<\/strong> Insertion des cl\u00e9s 37 puis 36<\/p><p><strong>Question 6<\/strong><\/p><p>La suppression de la cl\u00e9 17 entra\u00eene une sous-occupation de la feuille contenant la cl\u00e9 17. On choisit ici de fusionner cette feuille avec sa s\u0153ur droite (feuille appartenant au m\u00eame n\u0153ud p\u00e8re). La cl\u00e9 m\u00e9diane 24 redescend dans la feuille r\u00e9sultat de la fusion. La fusion de deux feuilles peut \u00eatre suivie d&rsquo;un r\u00e9-\u00e9clatement si la feuille r\u00e9sultat de la fusion se trouve sur-occup\u00e9e. Lors de la fusion de 2 n\u0153uds (resp. feuilles), le choix du fr\u00e8re (resp. s\u0153ur) avec lequel effectuer la fusion peut \u00eatre syst\u00e9matique (fr\u00e8re droit ou fr\u00e8re gauche \u00e0 chaque fois) ou bien dynamique.\u00a0<\/p><p>Un choix dynamique permet de fusionner avec le n\u0153ud (resp. feuille) qui produira un r\u00e9sultat de fusion le plus stable possible, c&rsquo;est-\u00e0-dire ni sur-occup\u00e9 ni sous-occup\u00e9. Cette optimisation n\u00e9cessite cependant la lecture des deux fr\u00e8res (resp. s\u0153urs) pour un gain hypoth\u00e9tique.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20092 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd50.png\" alt=\"bdd indexation b-tree\" width=\"572\" height=\"175\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd50.png 572w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd50-300x92.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd50-18x6.png 18w\" sizes=\"(max-width: 572px) 100vw, 572px\" \/><\/p><p><strong>Figure 3.<\/strong> Suppression des cl\u00e9s 17 puis 31<\/p><p>La suppression de la cl\u00e9 31 introduit un probl\u00e8me particulier du fait qu&rsquo;elle n&rsquo;appartient pas \u00e0 une feuille. Pour supprimer une cl\u00e9 dans un n\u0153ud non feuille, on la remplace par la plus grande cl\u00e9 du sous-arbre gauche (cl\u00e9 29 dans l&rsquo;exemple pr\u00e9c\u00e9dent) ou par la plus petite cl\u00e9 du sous-arbre droit (cl\u00e9 32 dans l&rsquo;exemple) dont la cl\u00e9 \u00e0 supprimer est racine. La cl\u00e9 choisie doit \u00e0 son tour \u00eatre supprim\u00e9e de la feuille en utilisant la proc\u00e9dure de suppression classique.<\/p><p><strong>Question 7<\/strong><\/p><p>La structure d&rsquo;arbre-B permet les acc\u00e8s s\u00e9quentiels tri\u00e9s puisque les cl\u00e9s sont tri\u00e9es dans l&rsquo;arborescence. Cependant, un parcours s\u00e9quentiel tri\u00e9 de l&rsquo;arbre-B n\u00e9cessite, apr\u00e8s lecture de toutes les cl\u00e9s d&rsquo;une feuille (resp. d&rsquo;un n\u0153ud), de remonter au n\u0153ud p\u00e8re pour acc\u00e9der \u00e0 la feuille s\u0153ur droite (n\u0153ud fr\u00e8re droit) afin de continuer la lecture des cl\u00e9s dans l&rsquo;ordre tri\u00e9. Ainsi, un n\u0153ud p\u00e8re sera acc\u00e9d\u00e9 sur disque \u00e0 chaque lecture de l&rsquo;un de ses fils, afin de r\u00e9cup\u00e9rer l&rsquo;adresse de ce fils. Il en r\u00e9sulte qu&rsquo;une lecture s\u00e9quentielle tri\u00e9e des 12 n\u0153uds et feuilles de l&rsquo;arbre-B pr\u00e9sent\u00e9 n\u00e9cessite au total 20 E\/S.<\/p><p>Une optimisation de la structure d&rsquo;arbre-B pour les parcours s\u00e9quentiels tri\u00e9s consiste \u00e0 dupliquer toutes les cl\u00e9s stock\u00e9es dans les n\u0153uds non feuille au niveau des feuilles puis \u00e0 cha\u00eener ces feuilles entre elles dans l&rsquo;ordre du tri.\u00a0 L&rsquo;adresse de la premi\u00e8re feuille peut de plus \u00eatre stock\u00e9e dans le descripteur de fichier. Ainsi, un parcours s\u00e9quentiel tri\u00e9 ne n\u00e9cessite que la lecture des feuilles de l&rsquo;arbre. Ce type d&rsquo;arbre est appel\u00e9 arbre-B+ [Comer79]. L&rsquo;arbre-B+ correspondant \u00e0 l&rsquo;arbre-B est pr\u00e9sent\u00e9 Figure 4.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-20093 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd51.png\" alt=\"bdd indexation b-tree\" width=\"610\" height=\"129\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd51.png 610w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd51-300x63.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2024\/02\/bdd51-18x4.png 18w\" sizes=\"(max-width: 610px) 100vw, 610px\" \/><\/p><p><strong>Figure 4. <\/strong>\u00a0Arbre-B+ correspondant \u00e0 l&rsquo;arbre-B de la figure 2<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8d3cb20 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8d3cb20\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e64697e\" data-id=\"e64697e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9430f5a elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"9430f5a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-62ef121 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"62ef121\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e87ceae\" data-id=\"e87ceae\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-913025e elementor-widget elementor-widget-heading\" data-id=\"913025e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-index-mutliples\"><\/span>Exercice index mutliples<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-adb352c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"adb352c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e1149c2\" data-id=\"e1149c2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-724fcff elementor-widget elementor-widget-text-editor\" data-id=\"724fcff\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Dans le domaine des bases de donn\u00e9es, les recherches d&rsquo;articles se font g\u00e9n\u00e9ralement sur des crit\u00e8res multiples (exemple: rechercher les voitures de puissance sup\u00e9rieure \u00e0 10 cv et de marque Citro\u00ebn). Les organisations de fichier index\u00e9es avec un seul index privil\u00e9gient le traitement du crit\u00e8re de recherche le plus fr\u00e9quemment employ\u00e9 sur un fichier, en ordonnan\u00e7ant les articles sur disque en fonction de ce crit\u00e8re. Pour traiter efficacement des recherches multi-crit\u00e8res, il est possible de g\u00e9rer plusieurs indexes pour un m\u00eame fichier.<\/p><p>La solution consiste \u00e0 utiliser un index principal pla\u00e7ant (les donn\u00e9es sont tri\u00e9es selon cet index) et des indexes annexes, appel\u00e9s <em>indexes secondaires<\/em>. Un index secondaire est constitu\u00e9 sur un attribut (ou plusieurs) discriminant ou non et donne pour chaque valeur de l\u2019attribut les identifiants (souvent les adresses relatives) des articles ayant cette valeur. L\u2019attribut (ou le groupe d\u2019attributs) ainsi index\u00e9 est appel\u00e9 cl\u00e9 secondaire.\u00a0<\/p><p>Lors d&rsquo;une recherche sur cl\u00e9 secondaire, l\u2019acc\u00e8s \u00e0 l\u2019index secondaire (un arbre B ou B+) \u00a0d\u00e9livre les identifiants de tous les articles satisfaisant le crit\u00e8re de recherche. Ces articles sont ensuite r\u00e9cup\u00e9r\u00e9s un \u00e0 un via leurs identifiants, \u00e0 raison d&rsquo;au plus une E\/S par article. La cr\u00e9ation d&rsquo;un index secondaire introduit un co\u00fbt de stockage important. De plus, toute mise \u00e0 jour du fichier de donn\u00e9es entra\u00eene la mise \u00e0 jour de tous les index secondaires portant sur ce fichier. L&rsquo;utilisation d&rsquo;index secondaires doit donc \u00eatre restreinte \u00e0 des crit\u00e8res de recherche fr\u00e9quents.<\/p><p><strong>Question 1<\/strong><\/p><p>On d\u00e9sire utiliser une organisation bas\u00e9e sur une technique d&rsquo;arbre-B+\u00a0pour indexer les articles d&rsquo;un fichier selon plusieurs attributs, A1 \u00e9tant cl\u00e9 primaire (pla\u00e7ante) et A2, A3, \u2026 Ap \u00e9tant des cl\u00e9s secondaires. Pr\u00e9cisez comment doivent \u00eatre modifi\u00e9es les algorithmes d\u2019insertion, mise-\u00e0-jour et suppression d\u2019articles en fichiers.<\/p><p><strong>Question 2<\/strong><\/p><p>Dans le m\u00eame contexte o\u00f9 le fichier est plac\u00e9 sur A1 et index\u00e9 sur les cl\u00e9s secondaires A2, A3, \u2026 Ap, pr\u00e9cisez l\u2019algorithme d\u2019ex\u00e9cution d\u2019une restriction de crit\u00e8re ( A1 = v1 &amp; A2 = v2 \u2026 &amp; Ap = vp). Comment peut-on optimiser la recherche des articles pertinents\u00a0? Comment modifier l\u2019algorithme si certains \u00ab\u00a0et\u00a0\u00bb ( &amp; ) sont remplac\u00e9s par des \u00ab\u00a0ou\u00a0\u00bb ( | ), en supposant une forme normale disjonctive (et de ou)\u00a0?<\/p><p><strong>Question 3<\/strong><\/p><p>Dans le m\u00eame contexte o\u00f9 le fichier est plac\u00e9 sur A1 et index\u00e9 sur les cl\u00e9s secondaires A2, A3, \u2026 Ap, pr\u00e9cisez l\u2019algorithme d\u2019ex\u00e9cution d\u2019une restriction de crit\u00e8re ( A1 = v1 &amp; A2 = v2 \u2026 &amp; Ap = vp &amp; B1 = v\u20191 &amp; B2 = v\u20192 &amp; \u2026), les Bi \u00e9tant des attributs non index\u00e9s. Compte tenu d\u2019une fr\u00e9quence pr\u00e9visionnelle d\u2019interrogation et de mise \u00e0 jour sur un attribut, pr\u00e9cisez comment choisir si un attribut gagne \u00e0 \u00eatre index\u00e9 ou non\u00a0?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5e0e131 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5e0e131\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fe6a2a0\" data-id=\"fe6a2a0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e5a555b elementor-widget elementor-widget-toggle\" data-id=\"e5a555b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2401\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2401\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2401\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2401\"><p>\u00a0Les algorithmes de gestion des arbre-B+ introduits\u00a0 font l&rsquo;hypoth\u00e8se d&rsquo;un tri mono-crit\u00e8re (c-\u00e0-d, prenant en compte un seul attribut). Afin de prendre en compte plusieurs attributs dans la m\u00e9thode de placement, il suffit d&rsquo;adapter la fonction <em>Rech_dichoto<\/em>\u00a0 \u00e0 un tri multi-crit\u00e8res. La cl\u00e9 \u00e0 utiliser dans le tri est la concat\u00e9nation des attributs A1, A2, \u2026, An. La comparaison de 2 cl\u00e9s s\u2019effectue d&rsquo;abord sur l&rsquo;attribut A1. En cas d&rsquo;\u00e9galit\u00e9, on prend en compte la valeur de l&rsquo;attribut A2 et ainsi de suite. Une cl\u00e9 c1 est donc consid\u00e9r\u00e9e comme sup\u00e9rieure \u00e0 une cl\u00e9 c2 si ($i \/ c1.Ai &gt; c2.Ai) et (i=1 ou \u00ab\u00a0j&lt;i c1.Ai = c2.Ai).<\/p><p>Cette m\u00e9thode ne traite pas les diff\u00e9rents attributs de fa\u00e7on \u00e9quitable. Ainsi, si le crit\u00e8re de tri choisi est A1, A2, \u2026, An, il est possible d&rsquo;acc\u00e9l\u00e9rer les recherches en fonction d&rsquo;une cl\u00e9 compl\u00e8te ou en fonction d&rsquo;une cl\u00e9 partielle \u00e0 condition que cette cl\u00e9 partielle pr\u00e9serve les premiers attributs de la cl\u00e9 compl\u00e8te. Ainsi, une recherche de tous les articles tels que (A1=valeur1 et A2= valeur2) est possible. Par contre, une recherche de tous les articles tels que (A2=valeur1 et A3= valeur2) sans pr\u00e9ciser de valeur pour A1 ne peut pas \u00eatre acc\u00e9l\u00e9r\u00e9e par l&rsquo;arbre-B+.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>P\u00e1gina de inicio de an\u00e1lisis de software Wiki Ejercicios respondidos: claves de indexaci\u00f3n en una base de datos Los \u00edndices de la base de datos son procesados por\u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":4609,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-20068","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/20068","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=20068"}],"version-history":[{"count":7,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/20068\/revisions"}],"predecessor-version":[{"id":20526,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/20068\/revisions\/20526"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4609"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=20068"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}