B+Tree và ứng dụng

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về c&acirc;y B+ bằng c&aacute;c h&igrave;nh ảnh minh họa. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&aacute;c thao t&aacute;c được thực hiện tr&ecirc;n c&acirc;y B+.</p> <h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">C&acirc;y B+ hay B+ tree l&agrave; dạng cải tiến của c&acirc;y tự c&acirc;n bằng, trong đ&oacute; tất cả c&aacute;c gi&aacute; trị đều c&oacute; ở mức l&aacute;.</p> <p style="text-align: justify;">Một kh&aacute;i niệm quan trọng cần được hiểu trước khi t&igrave;m hiểu về B+ l&agrave; việc lập chỉ số đa mức. Trong lập chỉ số đa mức, chỉ số của c&aacute;c chỉ số được tạo như trong h&igrave;nh b&ecirc;n dưới. N&oacute; gi&uacute;p truy cập dữ liệu dễ d&agrave;ng hơn v&agrave; nhanh hơn.</p> <p><img style="width: 100%;" src="../../../public_files/12e90481-d3bd-4e0f-8752-41158ec9b938" alt="cay-B2-tree" /></p> <p id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;"><strong>Thuộc t&iacute;nh của c&acirc;y B+:</strong></p> <ul style="text-align: justify;"> <li>Tất cả c&aacute;c n&uacute;t l&aacute; đều ở c&ugrave;ng một mức.</li> <li>N&uacute;t gốc c&oacute; &iacute;t nhất hai c&acirc;y con.</li> <li>Mỗi n&uacute;t ngoại trừ gốc c&oacute; thể c&oacute; tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c55560395664142423" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span></span></span>&nbsp;n&uacute;t con v&agrave; &iacute;t nhất&nbsp;<span id="urvanov-syntax-highlighter-6106c5556039e398731331" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span></span></span>&nbsp;n&uacute;t con.</li> <li>Mỗi n&uacute;t c&oacute; thể chứa tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c555603a1836417126" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a v&agrave; tối thiểu l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6106c555603a2076280906" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code">&lceil;<span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span>&rceil;<span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a.</li> </ul> <p id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;"><strong>So s&aacute;nh giữa c&acirc;y B+ v&agrave; B-:</strong></p> <ul style="text-align: justify;"> <li>Con trỏ dữ liệu chỉ c&oacute; ở c&aacute;c n&uacute;t l&aacute; tr&ecirc;n c&acirc;y B+ trong khi con trỏ dữ liệu c&oacute; trong c&aacute;c n&uacute;t b&ecirc;n trong, n&uacute;t l&aacute; hoặc n&uacute;t gốc tr&ecirc;n c&acirc;y B-.</li> <li>C&aacute;c n&uacute;t l&aacute; kh&ocirc;ng li&ecirc;n kết với nhau tr&ecirc;n c&acirc;y B- trong khi ch&uacute;ng được kết nối tr&ecirc;n c&acirc;y B+.</li> <li>C&aacute;c thao t&aacute;c tr&ecirc;n c&acirc;y B+ nhanh hơn tr&ecirc;n c&acirc;y B-.</li> </ul> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">2. C&aacute;c thao t&aacute;c thực hiện tr&ecirc;n B+ tree</h2> <h3 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">2.1. T&igrave;m kiếm tr&ecirc;n B+ tree</h3> <p style="text-align: justify;">C&aacute;c bước sau được thực hiện để t&igrave;m kiếm dữ liệu trong B+ tree. C&acirc;y c&oacute; bậc l&agrave; m. Cho dữ liệu cần t&igrave;m l&agrave; k.</p> <ol style="text-align: justify;"> <li>Bắt đầu từ n&uacute;t gốc. So s&aacute;nh k với c&aacute;c kh&oacute;a ở n&uacute;t gốc&nbsp;<span id="urvanov-syntax-highlighter-6106c555603a5392955833" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">[</span><span class="crayon-v">k1</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k2</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k3</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">km</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">-</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">1</span><span class="crayon-sy">]</span></span></span>.</li> <li>Nếu&nbsp;<span id="urvanov-syntax-highlighter-6106c555603a6761336302" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">k</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">&lt;</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k1</span></span></span>, chuyển đến c&acirc;y con b&ecirc;n tr&aacute;i của n&uacute;t gốc.</li> <li>Nếu&nbsp;<span id="urvanov-syntax-highlighter-6106c555603a8104887492" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">k</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">=</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k1</span></span></span>, so s&aacute;nh k2. Nếu&nbsp;<span id="urvanov-syntax-highlighter-6106c555603aa557127293" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">k</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">&lt;</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k2</span></span></span>&nbsp;th&igrave; k nằm giữa k1 v&agrave; k2. V&igrave; vậy, t&igrave;m kiếm trong c&acirc;y con b&ecirc;n tr&aacute;i của k2.</li> <li>Nếu&nbsp;<span id="urvanov-syntax-highlighter-6106c555603ab217324142" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">k</span><span class="crayon-h">&nbsp;</span><span class="crayon-o">&gt;</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k2</span></span></span>, tiếp tục với&nbsp;<span id="urvanov-syntax-highlighter-6106c555603ad417945239" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">k3</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">k4</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-sy">.</span><span class="crayon-h">&nbsp;</span><span class="crayon-e">k</span><span class="crayon-sy">(</span><span class="crayon-v">m</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span></span></span>&nbsp;như ở bước 2 v&agrave; bước 3.</li> <li>Lặp lại c&aacute;c bước tr&ecirc;n cho đến khi đến được n&uacute;t l&aacute;.</li> <li>Nếu k tồn tại trong n&uacute;t l&aacute;, trả về true, nếu kh&ocirc;ng ta trả về gi&aacute; trị l&agrave; false.</li> </ol> <p style="text-align: justify;">V&iacute; dụ, ch&uacute;ng ta sẽ t&igrave;m kiếm k = 47 tr&ecirc;n c&acirc;y B+ b&ecirc;n dưới đ&acirc;y.</p> <ul> <li style="text-align: justify;">So s&aacute;nh k với n&uacute;t gốc.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/fc7a3d8c-2794-4a64-a180-7830876cfd3a" alt="cay-B2-tree-2" /></p> <ul> <li>V&igrave; k &gt; 26 n&ecirc;n chuyển sang c&acirc;y con b&ecirc;n phải.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/caa6c666-e01c-4dfc-b500-9ff9562aefe6" alt="cay-B2-tree-3" /></p> <ul> <li>So s&aacute;nh k với 34. V&igrave; k &gt; 34 n&ecirc;n so s&aacute;nh k với 47.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/d54bdfc2-fe18-413b-b480-0d498176b553" alt="cay-B2-tree-4" /></p> <ul> <li>V&igrave; k &ge; 47 n&ecirc;n đi sang c&acirc;y con b&ecirc;n phải.</li> <li>V&agrave; cuối c&ugrave;ng th&igrave; k được t&igrave;m thấy.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/abc9c748-b02d-4053-b8c0-edf8f1f28963" alt="cay-B2-tree-5" /></p> <p style="text-align: justify;"><strong>Độ phức tạp về mặt thời gian của thao t&aacute;c t&igrave;m kiếm</strong></p> <ul style="text-align: justify;"> <li>Nếu t&igrave;m kiếm tuyến t&iacute;nh được thực hiện b&ecirc;n trong một n&uacute;t, th&igrave; tổng độ phức tạp l&agrave; $O(log_t(n))$.</li> <li>Nếu sử dụng t&igrave;m kiếm nhị ph&acirc;n, th&igrave; tổng độ phức tạp l&agrave; $O(log_2(t) \times log_t(n))$</li> </ul> <h3 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;">2.2. Ch&egrave;n phần tử v&agrave;o c&acirc;y</h3> <p style="text-align: justify;">Việc ch&egrave;n một phần tử v&agrave;o c&acirc;y B+ bao gồm ba giai đoạn ch&iacute;nh: t&igrave;m kiếm n&uacute;t l&aacute; th&iacute;ch hợp, ch&egrave;n phần tử v&agrave; c&acirc;n bằng c&acirc;y.</p> <p style="text-align: justify;">Trước khi ch&egrave;n một phần tử v&agrave;o c&acirc;y B+, ta phải ghi nhớ những thuộc t&iacute;nh sau.</p> <ul style="text-align: justify;"> <li>N&uacute;t gốc c&oacute; &iacute;t nhất hai n&uacute;t con.</li> <li>Mỗi n&uacute;t ngoại trừ gốc c&oacute; thể c&oacute; tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c555603af793384670" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span></span></span>&nbsp;n&uacute;t con v&agrave; &iacute;t nhất&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b1850431058" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span></span></span>&nbsp;n&uacute;t con.</li> <li>Mỗi n&uacute;t c&oacute; thể chứa tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b2010902126" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a v&agrave; tối thiểu l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b4774803394" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code">&lceil;<span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span>&rceil;<span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a.</li> </ul> <p style="text-align: justify;">C&aacute;c bước sau được thực hiện để ch&egrave;n một phần tử.</p> <ol style="text-align: justify;"> <li>V&igrave; mọi phần tử đều được ch&egrave;n v&agrave;o n&uacute;t l&aacute;, ta sẽ chuyển đến n&uacute;t l&aacute; th&iacute;ch hợp.</li> <li>Ch&egrave;n kh&oacute;a v&agrave;o n&uacute;t l&aacute;.</li> </ol> <p style="text-align: justify;"><strong>Trường hợp I</strong></p> <ul style="text-align: justify;"> <li>Nếu n&uacute;t l&aacute; chưa đầy, ta sẽ ch&egrave;n kh&oacute;a v&agrave;o n&uacute;t l&aacute; theo thứ tự tăng dần.</li> </ul> <p style="text-align: justify;"><strong>Trường hợp II</strong></p> <ol style="text-align: justify;"> <li>Nếu n&uacute;t l&aacute; đầy, ch&egrave;n gi&aacute; trị kh&oacute;a v&agrave;o n&uacute;t l&aacute; theo thứ tự tăng dần v&agrave; c&acirc;n bằng c&acirc;y theo c&aacute;ch sau.</li> <li>Ngắt n&uacute;t ở vị tr&iacute; thứ&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b5886419199" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span></span></span>.</li> <li>Th&ecirc;m kh&oacute;a thứ&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b7043821650" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span></span></span>&nbsp;v&agrave;o n&uacute;t cha.</li> <li>Nếu n&uacute;t cha đ&atilde; đầy, ta sẽ l&agrave;m theo c&aacute;c bước từ 2 đến 3.</li> </ol> <p style="text-align: justify;">V&iacute; dụ, giả sử c&aacute;c phần tử được ch&egrave;n l&agrave; 2,4, 6, 8, 10.</p> <ul> <li style="text-align: justify;">Ch&egrave;n 2.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/258f0870-ef1a-4fed-b8c5-2b018efd8fb9" alt="cay-B2-tree-6" /></p> <ul> <li>Ch&egrave;n 4</li> </ul> <p><img style="width: 100%;" src="../../../public_files/6f207012-16fe-4c99-ac30-482a0693ad2d" alt="cay-B2-tree-7" /></p> <ul> <li>Ch&egrave;n 6</li> </ul> <p><img style="width: 100%;" src="../../../public_files/9809a115-89c2-4594-8904-180433b245cd" alt="cay-B2-tree-8" /></p> <ul> <li>Ch&egrave;n 8</li> </ul> <p><img style="width: 100%;" src="../../../public_files/443d0887-db94-47f7-b867-f1a73f52ee10" alt="cay-B2-tree-9" /></p> <ul> <li>Ch&egrave;n 10</li> </ul> <p><img style="width: 100%;" src="../../../public_files/e7930182-92b9-4eaf-89b9-488817cc2822" alt="cay-B2-tree-10" /></p> <p><img style="width: 100%;" src="../../../public_files/b2c24c00-bd04-42dd-b14a-8f52d20ddec7" alt="cay-B2-tree-11" /></p> <p><img style="width: 100%;" src="../../../public_files/13ce1ad0-ac4a-47e5-ac83-a77a41d19619" alt="cay-B2-tree-12" /></p> <p style="text-align: justify;">Độ phức tạp về thời gian của thao t&aacute;c ch&egrave;n l&agrave;: $O(t.log_t(n))$</p> <h3 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">2.3. Thao t&aacute;c x&oacute;a</h3> <p style="text-align: justify;">X&oacute;a một phần tử tr&ecirc;n c&acirc;y B + bao gồm ba giai đoạn ch&iacute;nh: t&igrave;m kiếm n&uacute;t cần x&oacute;a, x&oacute;a kh&oacute;a v&agrave; c&acirc;n bằng c&acirc;y nếu cần. Underflow l&agrave; t&igrave;nh huống khi số lượng kh&oacute;a trong một n&uacute;t &iacute;t hơn số lượng kh&oacute;a tối thiểu cần c&oacute;.</p> <p style="text-align: justify;">Trước khi thực hiện c&aacute;c bước dưới đ&acirc;y, ta cần biết những th&ocirc;ng tin như sau về một c&acirc;y B+ với mức m.</p> <ol style="text-align: justify;"> <li>Một n&uacute;t c&oacute; thể c&oacute; tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c555603b9056935331" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span></span></span>&nbsp;n&uacute;t con.</li> <li>Một n&uacute;t c&oacute; thể chứa tối đa&nbsp;<span id="urvanov-syntax-highlighter-6106c555603c1444973100" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">m</span><span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a.</li> <li>Một n&uacute;t phải c&oacute; tối thiểu&nbsp;&nbsp;<span id="urvanov-syntax-highlighter-6106c555603c3380137792" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code">&lceil;<span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span>&rceil;</span></span>&nbsp;n&uacute;t con.</li> <li>Một n&uacute;t (trừ n&uacute;t gốc) phải chứa tối thiểu&nbsp;<span id="urvanov-syntax-highlighter-6106c555603c5173679194" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code">&lceil;<span class="crayon-v">m</span><span class="crayon-o">/</span><span class="crayon-cn">2</span>&rceil;<span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>&nbsp;kh&oacute;a.</li> </ol> <p style="text-align: justify;">Trong khi x&oacute;a kh&oacute;a, ch&uacute;ng ta phải quan t&acirc;m đến c&aacute;c kh&oacute;a c&oacute; trong c&aacute;c n&uacute;t b&ecirc;n trong (tức l&agrave; chỉ số) v&igrave; c&aacute;c gi&aacute; trị sẽ bị dư thừa trong c&acirc;y B+. Ta sẽ t&igrave;m kiếm kh&oacute;a cần x&oacute;a rồi l&agrave;m theo c&aacute;c bước sau.</p> <p style="text-align: justify;"><strong>Trường hợp I</strong></p> <p style="text-align: justify;">Kh&oacute;a được x&oacute;a nằm ở n&uacute;t l&aacute; kh&ocirc;ng c&oacute; trong chỉ số (hoặc n&uacute;t b&ecirc;n trong). C&oacute; hai trường hợp:</p> <ul> <li style="text-align: justify;">C&oacute; nhiều hơn số lượng kh&oacute;a tối thiểu trong n&uacute;t. Chỉ cần thực hiện x&oacute;a kh&oacute;a.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/19780ddf-82bd-4b2a-b6c7-f3b3e0fe271a" alt="cay-B2-tree-13" /></p> <p><img style="width: 100%;" src="../../../public_files/c80dfc0e-a7a4-4277-9b1f-3c4708f203d7" alt="cay-B2-tree-14" /></p> <ul> <li style="text-align: justify;">C&oacute; một số lượng kh&oacute;a tối thiểu ch&iacute;nh x&aacute;c trong n&uacute;t. X&oacute;a kh&oacute;a v&agrave; mượn kh&oacute;a của n&uacute;t anh em liền kề. Th&ecirc;m kh&oacute;a trung gian của n&uacute;t anh em v&agrave;o n&uacute;t cha.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/72e6e193-9598-4690-8543-52d23ee523e1" alt="cay-B2-tree-15" /></p> <p><img style="width: 100%;" src="../../../public_files/14ab977c-7965-4fd3-b46b-e1ea06c0b3d5" alt="cay-B2-tree-16" /></p> <p><img style="width: 100%;" src="../../../public_files/7bb842dc-caae-4db5-9477-43e59c9017da" alt="cay-B2-tree-17" /></p> <p><strong>Trường hợp II</strong></p> <p style="text-align: justify;">Kh&oacute;a được x&oacute;a cũng c&oacute; trong c&aacute;c n&uacute;t b&ecirc;n trong. V&igrave; vậy, ta cũng phải x&oacute;a ch&uacute;ng khỏi c&aacute;c n&uacute;t b&ecirc;n trong. C&oacute; những trường hợp sau đ&acirc;y cho t&igrave;nh huống n&agrave;y.</p> <ul> <li style="text-align: justify;">Nếu c&oacute; nhiều hơn số lượng kh&oacute;a tối thiểu trong n&uacute;t, chỉ cần x&oacute;a kh&oacute;a khỏi n&uacute;t l&aacute; v&agrave; x&oacute;a cả kh&oacute;a khỏi n&uacute;t b&ecirc;n trong. Lấp đầy khoảng trống trong n&uacute;t b&ecirc;n trong bằng n&uacute;t kế nhiệm Inorder.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/5cbb4088-c76e-42fd-ab91-fc9a937c6d5f" alt="cay-B2-tree-18" /></p> <p><img style="width: 100%;" src="../../../public_files/35f6cbf8-9e65-46fb-9976-2b7d359ccc7b" alt="cay-B2-tree-19" /></p> <p><img style="width: 100%;" src="../../../public_files/66780df9-ba65-4ec4-9481-3ff9007daf1c" alt="cay-B2-tree-20" /></p> <ul> <li style="text-align: justify;">Nếu c&oacute; số lượng kh&oacute;a tối thiểu trong n&uacute;t, th&igrave; ta sẽ x&oacute;a kh&oacute;a v&agrave; mượn kh&oacute;a từ n&uacute;t anh em trực tiếp của n&oacute; (th&ocirc;ng qua n&uacute;t cha). Lấp đầy v&agrave;o kh&ocirc;ng gian trống được tạo trong chỉ số (n&uacute;t b&ecirc;n trong) bằng kh&oacute;a được mượn.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/595200bb-d4f2-40c4-91e1-ecb6749d29d5" alt="cay-B2-tree-21" /></p> <p><img style="width: 100%;" src="../../../public_files/168d6148-454e-465c-8c20-fc28246ae9a4" alt="cay-B2-tree-22" /></p> <p><img style="width: 100%;" src="../../../public_files/adb2dd2c-e926-4a24-994d-3c646b485061" alt="cay-B2-tree-23" /></p> <ul> <li style="text-align: justify;">Trường hợp n&agrave;y tương tự như Trường hợp II (1) nhưng ở đ&acirc;y, kh&ocirc;ng gian trống được tạo ra ph&iacute;a tr&ecirc;n n&uacute;t cha trực tiếp. Sau khi x&oacute;a kh&oacute;a, ta sẽ hợp nhất kh&ocirc;ng gian trống với c&aacute;c n&uacute;t anh em. Lấp đầy v&agrave;o chỗ trống trong n&uacute;t &ocirc;ng (n&uacute;t cha của n&uacute;t cha) bằng n&uacute;t kế nhiệm Inorder.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/c8fa86c8-f5c3-41e3-b0bb-3ca4a744b8b7" alt="cay-B2-tree-24" /></p> <p><img style="width: 100%;" src="../../../public_files/2010ca3e-a054-4d81-8f72-05a6bacc4f80" alt="cay-B2-tree-25" /></p> <p><img style="width: 100%;" src="../../../public_files/c38df859-06a7-45d7-8f5e-5b443956ee65" alt="cay-B2-tree-26" /></p> <p><img style="width: 100%;" src="../../../public_files/d0185fcc-0990-47f0-b186-4a6ad7b76aa2" alt="cay-B2-tree-27" /></p> <p><strong>Trường hợp III</strong></p> <ul> <li>Trong trường hợp n&agrave;y, chiều cao của c&acirc;y bị thu hẹp.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/9e995c37-7e56-4653-926e-d94f9a37256d" alt="cay-B2-tree-28" /></p> <p><img style="width: 100%;" src="../../../public_files/3584fbe2-8388-4b42-920e-de1bdfcfeb95" alt="cay-B2-tree-29" /></p> <p><img style="width: 100%;" src="../../../public_files/394e7959-c639-4088-981d-d123b75b8a55" alt="cay-B2-tree-30" /></p> <h2 id="ftoc-heading-8" class="ftwp-heading" style="text-align: justify;">3. Ứng dụng</h2> <ul style="text-align: justify;"> <li>Lập chỉ số đa mức.</li> <li>C&aacute;c thao t&aacute;c, bao gồm ch&egrave;n, x&oacute;a v&agrave; t&igrave;m kiếm, được thực hiện nhanh hơn tr&ecirc;n B+ tree.</li> <li>Lập chỉ số cho cơ sở dữ liệu.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về cấu tr&uacute;c dữ liệu c&acirc;y B+. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>