https://wiki.algo.informatik.tu-darmstadt.de/index.php?action=history&feed=atom&title=B-tree%3A_split 2026-10-27T18:57:31Z Revision history for this page on the wiki MediaWiki 1.46.2 https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=652&oldid=prev 2014-10-05T08:42:54Z

<p>Luedecke moved page <a href="/B-Tree:Split-Child" class="mw-redirect" title="B-Tree:Split-Child">B-Tree:Split-Child</a> to <a href="/B-tree:_split" title="B-tree: split">B-tree: split</a></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <tr class="diff-title" lang="en"> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 08:42, 5 October 2014</td> </tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div> </td></tr></table>

Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=304&oldid=prev 2014-09-25T20:25:15Z

<p><span class="autocomment">Pseudocode</span></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:25, 25 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  B-TREE-SPLIT-CHILD(&#039;&#039;x&#039;&#039;, &#039;&#039;i&#039;&#039;)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  B-TREE-SPLIT-CHILD(&#039;&#039;x&#039;&#039;, &#039;&#039;i&#039;&#039;)</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   1 &#039;&#039;z&#039;&#039; = ALLOCATE-NODE()</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   1 &#039;&#039;z&#039;&#039; = ALLOCATE-NODE()</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   2 ''y'' = ''x''.''c''<del style="font-weight: bold; text-decoration: none;">iiiiiiiiiiiii</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   2 ''y'' = ''x''.''c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;i&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   3 &#039;&#039;z&#039;&#039;.&#039;&#039;leaf&#039;&#039; = &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   3 &#039;&#039;z&#039;&#039;.&#039;&#039;leaf&#039;&#039; = &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   4 &#039;&#039;z.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   4 &#039;&#039;z.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   5 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 &#039;&#039;&#039;to&#039;&#039;&#039; &#039;&#039;t&#039;&#039; - 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   5 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 &#039;&#039;&#039;to&#039;&#039;&#039; &#039;&#039;t&#039;&#039; - 1</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   6          ''z.key''<del style="font-weight: bold; text-decoration: none;">jjjjj </del>= ''y.key''<del style="font-weight: bold; text-decoration: none;">jjjjj</del>+<del style="font-weight: bold; text-decoration: none;">tttt</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   6          ''z.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j&lt;/sub&gt; </ins>= ''y.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j </ins>+ <ins style="font-weight: bold; text-decoration: none;">t&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   9              ''z.c''<del style="font-weight: bold; text-decoration: none;">jjjjj </del>= ''y.c''<del style="font-weight: bold; text-decoration: none;">jjjj</del>+<del style="font-weight: bold; text-decoration: none;">tttt</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   9              ''z.c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j&lt;/sub&gt; </ins>= ''y.c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j </ins>+ <ins style="font-weight: bold; text-decoration: none;">t&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  12          ''x.c''<del style="font-weight: bold; text-decoration: none;">jjjj</del>+<del style="font-weight: bold; text-decoration: none;">111 </del>= ''x.c''<del style="font-weight: bold; text-decoration: none;">jjjj</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  12          ''x.c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j </ins>+ <ins style="font-weight: bold; text-decoration: none;">1&lt;/sub&gt; </ins>= ''x.c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  13 ''x.c''<del style="font-weight: bold; text-decoration: none;">iiii</del>+<del style="font-weight: bold; text-decoration: none;">1111 </del>= ''z''</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  13 ''x.c''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;i </ins>+ <ins style="font-weight: bold; text-decoration: none;">1&lt;/sub&gt; </ins>= ''z''</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  14 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  14 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  15          ''x.key''<del style="font-weight: bold; text-decoration: none;">iiii </del>= ''y.key''<del style="font-weight: bold; text-decoration: none;">jjjj</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  15          ''x.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;i&lt;/sub&gt; </ins>= ''y.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;j&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  16 ''x.key''<del style="font-weight: bold; text-decoration: none;">iiii </del>= ''y.key''<del style="font-weight: bold; text-decoration: none;">ttttttt</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  16 ''x.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;i&lt;/sub&gt; </ins>= ''y.key''<ins style="font-weight: bold; text-decoration: none;">&lt;sub&gt;t&lt;/sub&gt;</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  17 &#039;&#039;x.n&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  17 &#039;&#039;x.n&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  18 DISK-WRITE(&#039;&#039;y&#039;&#039;)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  18 DISK-WRITE(&#039;&#039;y&#039;&#039;)</div></td></tr> </table>

Lkw https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=236&oldid=prev 2014-09-22T17:24:16Z

<p><span class="autocomment">Pseudocode</span></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:24, 22 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11">Line 11:</td> <td colspan="2" class="diff-lineno">Line 11:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   9 <del style="font-weight: bold; text-decoration: none;">            </del>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   9 <ins style="font-weight: bold; text-decoration: none;">            </ins>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td></tr> </table>

Lkw https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=235&oldid=prev 2014-09-22T17:24:08Z

<p><span class="autocomment">Pseudocode</span></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:24, 22 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11">Line 11:</td> <td colspan="2" class="diff-lineno">Line 11:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   9 <del style="font-weight: bold; text-decoration: none;">              </del>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   9 <ins style="font-weight: bold; text-decoration: none;">            </ins>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td></tr> </table>

Lkw https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=234&oldid=prev 2014-09-22T17:23:36Z

<p><span class="autocomment">Pseudocode</span></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:23, 22 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11">Line 11:</td> <td colspan="2" class="diff-lineno">Line 11:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   9 <del style="font-weight: bold; text-decoration: none;">                </del>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   9 <ins style="font-weight: bold; text-decoration: none;">              </ins>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td></tr> </table>

Lkw https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=233&oldid=prev 2014-09-22T17:23:14Z

<p><span class="autocomment">Pseudocode</span></p> <table style="background-color: #fff; color: #202122;" data-mw-interface=""> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:23, 22 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11">Line 11:</td> <td colspan="2" class="diff-lineno">Line 11:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   8          &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>   9 <del style="font-weight: bold; text-decoration: none;">                    </del>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>   9 <ins style="font-weight: bold; text-decoration: none;">                </ins>''z.c''jjjjj = ''y.c''jjjj+tttt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17">Line 17:</td> <td colspan="2" class="diff-lineno">Line 17:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  13 &#039;&#039;x.c&#039;&#039;iiii+1111 = &#039;&#039;z&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  13 &#039;&#039;x.c&#039;&#039;iiii+1111 = &#039;&#039;z&#039;&#039;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  14 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  14 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>  15 <del style="font-weight: bold; text-decoration: none;">      </del>''x.key''iiii = ''y.key''jjjj</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>  15 <ins style="font-weight: bold; text-decoration: none;">          </ins>''x.key''iiii = ''y.key''jjjj</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  16 &#039;&#039;x.key&#039;&#039;iiii = &#039;&#039;y.key&#039;&#039;ttttttt</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  16 &#039;&#039;x.key&#039;&#039;iiii = &#039;&#039;y.key&#039;&#039;ttttttt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  17 &#039;&#039;x.n&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>  17 &#039;&#039;x.n&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1</div></td></tr> </table>

Lkw https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=232&oldid=prev 2014-09-22T17:22:43Z

<p>Created page with &quot;== Pseudocode == &lt;code&gt; B-TREE-SPLIT-CHILD(&#039;&#039;x&#039;&#039;, &#039;&#039;i&#039;&#039;) 1 &#039;&#039;z&#039;&#039; = ALLOCATE-NODE() 2 &#039;&#039;y&#039;&#039; = &#039;&#039;x&#039;&#039;.&#039;&#039;c&#039;&#039;iiiiiiiiiiiii 3 &#039;&#039;z&#039;&#039;.&#039;&#039;leaf&#039;&#039; = &#039;&#039;y.leaf&#039;&#039; 4 &#039;&#039;z.n&#039;&#039; = &#039;&#039;t&#039;...&quot;</p> <p><b>New page</b></p><div>== Pseudocode == <br /> <br /> &lt;code&gt;<br /> B-TREE-SPLIT-CHILD(&#039;&#039;x&#039;&#039;, &#039;&#039;i&#039;&#039;)<br /> 1 &#039;&#039;z&#039;&#039; = ALLOCATE-NODE()<br /> 2 &#039;&#039;y&#039;&#039; = &#039;&#039;x&#039;&#039;.&#039;&#039;c&#039;&#039;iiiiiiiiiiiii<br /> 3 &#039;&#039;z&#039;&#039;.&#039;&#039;leaf&#039;&#039; = &#039;&#039;y.leaf&#039;&#039;<br /> 4 &#039;&#039;z.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1<br /> 5 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 &#039;&#039;&#039;to&#039;&#039;&#039; &#039;&#039;t&#039;&#039; - 1<br /> 6 &#039;&#039;z.key&#039;&#039;jjjjj = &#039;&#039;y.key&#039;&#039;jjjjj+tttt<br /> 7 &#039;&#039;&#039;if&#039;&#039;&#039; not &#039;&#039;y.leaf&#039;&#039;<br /> 8 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = 1 to t<br /> 9 &#039;&#039;z.c&#039;&#039;jjjjj = &#039;&#039;y.c&#039;&#039;jjjj+tttt<br /> 10 &#039;&#039;y.n&#039;&#039; = &#039;&#039;t&#039;&#039; - 1 <br /> 11 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1 &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039; + 1<br /> 12 &#039;&#039;x.c&#039;&#039;jjjj+111 = &#039;&#039;x.c&#039;&#039;jjjj<br /> 13 &#039;&#039;x.c&#039;&#039;iiii+1111 = &#039;&#039;z&#039;&#039;<br /> 14 &#039;&#039;&#039;for&#039;&#039;&#039; &#039;&#039;j&#039;&#039; = &#039;&#039;x.n&#039;&#039; &#039;&#039;&#039;downto&#039;&#039;&#039; &#039;&#039;i&#039;&#039;<br /> 15 &#039;&#039;x.key&#039;&#039;iiii = &#039;&#039;y.key&#039;&#039;jjjj<br /> 16 &#039;&#039;x.key&#039;&#039;iiii = &#039;&#039;y.key&#039;&#039;ttttttt<br /> 17 &#039;&#039;x.n&#039;&#039; = &#039;&#039;x.n&#039;&#039; + 1<br /> 18 DISK-WRITE(&#039;&#039;y&#039;&#039;)<br /> 19 DISK-WRITE(&#039;&#039;z&#039;&#039;)<br /> 20 DISK-WRITE(&#039;&#039;x&#039;&#039;)<br /> &lt;/code&gt;</div>

Lkw