B树的生成
flyfish 2015-7-19
从空树開始构建一棵B树 逐个插入keyword
规则:
除根结点之外的全部非终端结点至少有?m/2?<script type="math/tex" id="MathJax-Element-3053">\left \lceil m/2 \right \rceil</script>棵子树,所以keyword的个数必须 n为keyword个数
?m/2?-1?<script type="math/tex" id="MathJax-Element-3054">\leqslant </script>n。
依照A0,K1,A1。K2,A2,…,Kn,An
也就是指针个数比keyword个数多一个
由于树中每一个结点至多有m 棵子树。所以该结点的keyword个数不能超过m-1
也就是,keyword个数的阈值 ?m/2??1<script type="math/tex" id="MathJax-Element-3055"> \left \lceil m/2 \right \rceil-1</script>?n<script type="math/tex" id="MathJax-Element-3056">\leqslant n</script>?m?1<script type="math/tex" id="MathJax-Element-3057">\leqslant m-1</script>
每次插入一个keyword不是在树中加入一个叶子结点,由于这样不再是有效的B树而是首先在最低层的某个非终端结点中加入一个keyword,若该结点的keyword个数不超过m-1,则插入完毕,否则要产生结点的“分裂”
绿色:keyword个数
红色:指针
蓝色:keyword
构建Degree为3keyword从1到7的B树
普通情况下,结点可例如以下实现分裂 引用自严蔚敏《数据结构》
如果*p结点中已有m-1个keyword。当插入一个keyword之后。结点中含有信息为:
(m。A0<script type="math/tex" id="MathJax-Element-3058">A_0</script>,(K1<script type="math/tex" id="MathJax-Element-3059">K_1</script>。A1<script type="math/tex" id="MathJax-Element-3060">A_1</script>)。…。(Km<script type="math/tex" id="MathJax-Element-3061">K_m</script>,Am<script type="math/tex" id="MathJax-Element-3062">A_m</script>)
且当中 Ki<script type="math/tex" id="MathJax-Element-3063">K_i</script><Ki<script type="math/tex" id="MathJax-Element-3064">K_i </script>+<script type="math/tex" id="MathJax-Element-3065">_+</script>1<script type="math/tex" id="MathJax-Element-3066">_1</script> , 1?<script type="math/tex" id="MathJax-Element-3067">\leqslant</script>i< m
此时可将*P节点分裂为*P和*P’两个结点,
*p结点中含有信息
?m/2?<script type="math/tex" id="MathJax-Element-3068">\left \lceil m/2 \right \rceil</script>-1。A0<script type="math/tex" id="MathJax-Element-3069">A_0</script>,(K1<script type="math/tex" id="MathJax-Element-3070">K_1</script>,A1<script type="math/tex" id="MathJax-Element-3071">A_1</script>),…,(K?m/2?<script type="math/tex" id="MathJax-Element-3072">K_\left \lceil m/2 \right \rceil</script>?<script type="math/tex" id="MathJax-Element-3073">_-</script>1<script type="math/tex" id="MathJax-Element-3074">_1</script>。A?m/2?<script type="math/tex" id="MathJax-Element-3075">A_\left \lceil m/2 \right \rceil</script>?<script type="math/tex" id="MathJax-Element-3076">_-</script>1<script type="math/tex" id="MathJax-Element-3077">_1</script>)
*p’结点中含有信息
m-?m/2?<script type="math/tex" id="MathJax-Element-3078">\left \lceil m/2 \right \rceil</script>,A?m/2?<script type="math/tex" id="MathJax-Element-3079">A_\left \lceil m/2 \right \rceil</script>。(K?m/2?<script type="math/tex" id="MathJax-Element-3080">K_\left \lceil m/2 \right \rceil</script>+<script type="math/tex" id="MathJax-Element-3081">_+</script>1<script type="math/tex" id="MathJax-Element-3082">_1</script>,A?m/2?<script type="math/tex" id="MathJax-Element-3083">A_\left \lceil m/2 \right \rceil</script>+<script type="math/tex" id="MathJax-Element-3084">_+</script>1<script type="math/tex" id="MathJax-Element-3085">_1</script> ),… ,(Km<script type="math/tex" id="MathJax-Element-3086">K_m</script>。Am<script type="math/tex" id="MathJax-Element-3087">A_m</script>)
而keywordK?m/2?<script type="math/tex" id="MathJax-Element-3088">_\left \lceil m/2 \right \rceil</script>和指针*p’一起插入到*p的双亲结点中.
简化理解
m为B树的阶,n为节点的个数
若在一个包括n<m?1<script type="math/tex" id="MathJax-Element-3089">n
但若把一个新的keyword插入到包括m-1个keyword的结点中,则将引起结点的分裂。
生成一新结点,把原结点上的keywordK按升序排序,也就是 Ki<script type="math/tex" id="MathJax-Element-3090">K_i</script><Ki<script type="math/tex" id="MathJax-Element-3091">K_i </script>+<script type="math/tex" id="MathJax-Element-3092">_+</script>1<script type="math/tex" id="MathJax-Element-3093">_1</script> 。
满足:左边的小于中间的keyword;右边的大于中间的keyword,从中间位置把keyword(不包括中间位置的keyword)分成两部分。
左部分所含keyword放在旧结点中。右部分所含keyword放在新结点中,中间位置的keyword连同新结点的存储位置(指向新节点的指针)插入到双亲结点中。
如果双亲结点的keyword个数也超过m-1,则要再分裂,再往上插入,此时B树可能朝着根的方向生长。
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>