📄 del.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> <meta name="description" content="NTFS Documentation"> <link rel="stylesheet" type="text/css" href="../../style/ntfsdoc.css"> <link rel="icon" href="../../style/ntfsicon.png" type="image/png"> <link rel="start" type="text/html" href="../../index.html" title="NTFS Documentation"> <link rel="next" href="index.html" title="B*Trees - NTFS Directory Trees"> <link rel="previous" href="add.html" title="Adding nodes"> <link rel="contents" href="../../index.html"> <title>Deleting, NTFS Directory Trees - Concept - NTFS Documentation</title> </head> <body> <table border="0" class="toolbar" summary="" cellspacing="0"> <tr> <td class="toolbar"><div class="toolbar"><a accesskey="1" class="toolbar" href="../../index.html">Home</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="2" class="toolbar" href="../../files/index.html">Files</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="3" class="toolbar" href="../../attributes/index.html">Attributes</a></div></td> <td class="toolbar"><div class="toolbar"><a accesskey="4" class="toolbar" href="../../concepts/index.html">Concepts</a></div></td> <td class="toolbar"><a accesskey="5" class="toolbar" href="../help/glossary.html">Glossary</a></td> </tr> </table> <h1>Concept - B*Trees - NTFS Directory Trees</h1> <a class="prevnext" accesskey="," href="add.html">Previous</a> <a class="prevnext" accesskey="." href="index.html">Next</a> <p> <a class="visible" href="index.html">Home</a> <a class="visible" href="add.html">Add</a> <a class="visible" href="del.html">Delete</a> </p> <h2>Deleting nodes in B*Trees - NTFS Directory Trees</h2> <p> For the deletion examples we'll start very simply then get complicated very fast. One large example shows all the ways in which delete affects the tree. </p> <a name="del01"></a> <div class="figure">Figure 1</div> <img src="del/01.png"><br> <p> Starting with a simple node, we delete <q>E</q>. </p> <a name="del02"></a> <div class="figure">Figure 2</div> <img src="del/02.png"><br> <p> Then we delete <q>A</q>. </p> <a name="del03"></a> <div class="figure">Figure 3</div> <img src="del/03.png"><br> <p> This leaves us with an empty node. </p> <a name="del04"></a> <div class="figure">Figure 4</div> <img src="del/04.png"><br> <p> Now we start with a large example tree. We want to delete <q>G</q>. It's got children, so we find the successor <q>J</q>, delete <q>G</q> and put <q>J</q> in its place. If the key doesn't have any children, this this stage can be skipped. </p> <a name="del05"></a> <div class="figure">Figure 5</div> <img src="del/05.png"><br> <p> Now we have transformed the problem into a leaf being deleted. Unfortunately this leaves us with a deficient node <q>!</q>. Our siblings don't have any keys we can steal to make up our numbers, so to fix this, we will have to combine with a sibling. </p> <a name="del06"></a> <div class="figure">Figure 6</div> <img src="del/06.png"><br> <p> We have demoted <q>K</q> and adopted <q>O</q> from our right-hand sibling. Unfortunately that leaves us with a deficient node <q>!</q>, so we work on that node next. This time we have a sibling with a key we can steal. To keep the tree in order, we will promote <q>E</q> and demote <q>J</q>. </p> <a name="del07"></a> <div class="figure">Figure 7</div> <img src="del/07.png"><br> <p> If you look closely, you will see that one of the nodes (containing <q>F</q>) has swapped sides of the tree. Because the pointers on-disk only point downwards, the the <q>F</q> node isn't changed. </p> <p> Once a steal has occurred, the operation is complete. </p> <br> <a class="contact" href="../help/license.html">Copyright (C)</a> <a class="contact" href="http://validator.w3.org/check?uri=http://linux-ntfs.sourceforge.net/ntfs/concepts/index.html">Validate HTML</a> <a class="contact" href="http://jigsaw.w3.org/css-validator/validator?uri=http://linux-ntfs.sourceforge.net/ntfs/concepts/index.html">Validate CSS</a> <img src="http://sourceforge.net/sflogo.php?group_id=13956" width="1" height="1" border="0" alt="SourceForge"> </body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -