Home
Công nghệ thông tin
Lập trình
Cấu trúc dữ liệu B+Tree và ứng dụng trong bài toán xử lý tập có thứ tự
Cấu trúc dữ liệu B+Tree và ứng dụng trong bài toán xử lý tập có thứ tự
C u trúc d li u B+Tree và ng d ng trong bài toán x lý t p có th ấ ữ ệ ứ ụ ử ậ ứ
tự
Gi i thi uớ ệ
Hi, xin chào m i ng i.ọ ườ
Lâu r i m i d o quanh 1 vòng các blog c a Vi t Nam th y blog này phát ồ ớ ạ ủ ệ ấ
tri n quá t nhiên c m th y mu n tham gia giao l u chia s ki n th c cùng ể ự ả ấ ố ư ẻ ế ứ
m i ng i đ cùng nhau góp 1 ph n nh cho s phát tri n ngành IT Vi t ọ ườ ể ầ ỏ ự ể ệ
Nam. Gi i thi u s qua mình t ng là sinh viên Bách Khoa Hà N i khóa ớ ệ ơ ừ ộ
Hedspi K52 và c u du h c sinh tr ng Keio Nh t B n. Hi n t i thì mình ự ọ ườ ậ ả ệ ạ
đang làm cho cty sàn giao d ch ti n mã hóa c a Nh t B n là Bitbank.ị ề ủ ậ ả
Bài toán
Vào v n đ chính hôm nay mình s gi i thi u 1 c u trúc d li u gi i thu t ấ ề ẽ ớ ệ ấ ữ ệ ả ậ
là BTree mà c th h n là B+Tree và ng d ng c a nó trong vi c gi i ụ ể ơ ứ ụ ủ ệ ả
quy t 1 bài toán nhìn qua thì th y r t đ n gi n nh ng đế ấ ấ ơ ả ư ể scale up v i kích ớ
th c d li u l n và các thao tác di n ra v i t n su t cao thì th c s l i là ướ ữ ệ ớ ễ ớ ầ ấ ự ự ạ
1 v n đ khác.ấ ề
Bài toán đ t ra nh sau chúng ta có 1 t p các s đ c s p x p theo th t ặ ư ậ ố ượ ắ ế ứ ự
tăng d n ví d nhầ ụ ư [1,2,3,5,7,8,9,12]. Và yêu c u đ t ra là chúng ta ph i ầ ặ ả
thêm ho c xóa b t 1 s ph n t sao cho v n đ m b o th t tăng d n. R t ặ ớ ố ầ ử ẫ ả ả ứ ự ầ ấ
đ n gi n đúng không và nh bình th ng chúng ta cũng có cách gi i quy t ơ ả ư ườ ả ế
đ n gi n dùng c u trúc d li u m ng và gi i thu t tìm ki m tu n t (ơ ả ấ ữ ệ ả ả ậ ế ầ ự linear
search) (nh ng ph n code minh h a trong bài vi t mình s s ữ ầ ọ ế ẽ ử
d ngụ typescript).
Cách gi i đ n thu nả ơ ầ
const arr = [1,2,3,5,7,8,9,12];
// insert
function insert(value: number) {
// tìm v trí ph n t đ u tiên l n h n ho c b ng ${value}ị ầ ử ầ ớ ơ ặ ằ
const pos = arr.find((a) => a >= value);
// chèn value vào v trí nàyị
arr.splice(pos, 0, value);
}
// delete
function delete(value: number) {
// tìm v trí ph n t đ u tiên l n h n ho c b ng ${value}ị ầ ử ầ ớ ơ ặ ằ
const pos = arr.find((a) => a >= value);
// xóa v trí này n u tìm th yị ế ấ
if (arr[pos] === value) {
arr.splice(pos, 1);
}
}
D th y đ ph c t p cho m i thao tácễ ấ ộ ứ ạ ỗ insert ho cặ delete c a cách làm này ủ
là O(n) v iớ n = arr.length. Gi s v trí c n tìm là k (0 <= k <= n) chúng ta ả ử ị ầ
c n k + 1 phép so sánh đ tìm đ c v trí này sau đó đầ ể ượ ị ể insert hay delete ta
cũng c n reindex toàn b các ph n t phía sau t ng c ng là c n n thao tác ầ ộ ầ ử ổ ộ ầ
t c làứ O(n) đ hoàn thành.ể
C i ti n v i binary search trên arrayả ế ớ
V i c u trúc d li u m ng array chúng ta có th truy c p đ n ph n t v ớ ấ ữ ệ ả ể ậ ế ầ ử ở ị
trí b t kỳ v i th i gian O(1). T n d ng đi u này ta có th áp d ngấ ớ ờ ậ ụ ề ể ụ binary
search trên m ng đã s p x p đ tăng t c thao tác tìm ki m.ả ắ ế ể ố ế
function binarySearchPosition(value: number, firstIndex: number, lastIndex:
number): number {
if (firstIndex === lastIndex) {
return firstIndex;
}
const middleIndex = Math.floor((firstIndex + lastIndex) / 2);
if (arr[middleIndex] === value) {
return middleIndex;
}
return arr[middleIndex] < value
? binarySearchPosition(value, middleIndex + 1, lastIndex)
: binarySearchPosition(value, firstIndex, middleIndex);
}
Áp d ng hàm tìm ki m này chúng ta c i ti n cài đ t ban đ u b ng vi c thayụ ế ả ế ặ ầ ằ ệ
th dòng l nh tìm ki m tu n t nh sau:ế ệ ế ầ ự ư
// 'const pos = arr.find((a) => a >= value)' thay b ngằ
const pos = binarySearchPosition(value, 0, arr.length);
Ta th y cài đ t ph n search đã đ c c i ti n ch v i m i phép so sánh ấ ặ ầ ượ ả ế ở ỗ ớ ỗ
v i ph n t gi a s l ng m ng tìm ki m c a chúng ta đã gi m đi 1 n a ớ ầ ử ữ ố ượ ả ế ủ ả ử
ch không ph i ch gi m 1 nh cài đ t ban đ u. Ta làm đ c đi u này là doứ ả ỉ ả ư ặ ầ ượ ề
tính ch t có th truy c p đ n ph n t gi a 1 cách t c thì c a m ng. Và ấ ể ậ ế ầ ử ữ ứ ủ ả
đi u này cũng có s đánh đ i khi thao tác modify m ng (insert, delete) v n ề ự ổ ả ẫ
c n đ m b o tính ch t này b ng cách ph i reindex toàn b các ph n t phíaầ ả ả ấ ằ ả ộ ầ ử
sau v trí b thay đ i. Th i gian tính toán c a thao tác này tùy thu c v trí ị ị ổ ờ ủ ộ ị
thay đ i nh ng v trung bình mà nói c b n v n là O(n) m c dù c i ti n là ổ ư ề ơ ả ẫ ặ ả ế
r t đáng k so v i cài đ t ban đ u.ấ ể ớ ặ ầ
chi u h ng khác c u trúc d li uỞ ề ướ ấ ữ ệ LinkedList cho phép insert, delete vở ị
trí xác đ nh v i th i gian t c thì O(1) nh ng v iị ớ ờ ứ ư ớ LinkedList không có cách
nào đ truy c p nhanh ph n t gi a mà không ph i duy t nh trên m ng doể ậ ầ ử ữ ả ệ ư ả
đó v n ph i s d ng tìm ki m tu n t v i đ ph c t p O(n).ẫ ả ử ụ ế ầ ự ớ ộ ứ ạ
R t may chúng ta có gi i pháp k t h p đi m m nh c a c 2 c u trúc d ấ ả ế ợ ể ạ ủ ả ấ ữ
li u k trên làệ ể Array và LinkedList.
C i ti n v i c u trúc d li u B+treeả ế ớ ấ ữ ệ
B+Tree có th đ c nhìn d i góc đ nh là s k t h p ể ượ ướ ộ ư ự ế ợ
gi aữ Array và LinkedList:
Tìm ki m (search)ế: m i phép so sánh cho phép ta lo i 1 c s ph n ỗ ạ ơ ố ầ
t đ đ n v i v trí c n tìm nhanh h n.ử ể ế ớ ị ầ ơ
Ch nh s a (modify)ỉ ử : thao tác insert, delete 1 v trí xác đ nh không ở ị ị
làm nh h ng đ n toàn b các ph n t còn l i.ả ưở ế ộ ầ ử ạ
B+Tree là c u trúc d ng cây tìm ki m và là t ng quát c a cây tìm ki m nh ấ ạ ế ổ ủ ế ị
phân (Binary Search Tree - BST) v i 1 node g c (ớ ố root), các node trong
(internal node) có ch a các node con và các node d i cùng không ch a ứ ướ ứ
node con g i là node lá (ọleaf node).
Các node trong ch aứ n ph n t g i là khóa tìm ki m (ầ ử ọ ế key) và t ng ươ
ng làứ n+1 node con có tính ch t:ấ
key[i-1] <= {child[i].data} < key[i]
S l ng khóa và node con trong 1 node dao đ ng trong 1 kho ng ố ượ ộ ả
h ng s nh đ c xác đ nh b i giá trằ ố ỏ ượ ị ở ị order (d ch là b c) c a B+tree.ị ậ ủ
T t c các ph n t c a t p c n qu n lý đ u n m node lá.ấ ả ầ ử ủ ậ ầ ả ề ằ ở
T t c node lá đ u có cùng đ cao và đ c liên k t nhau theo th t ấ ả ề ộ ượ ế ứ ự
b ng pointer nhằ ư linkedlist.
Chúng ta có th tìm ki m nhanh trên cây này b ng cách b t đ u t node g cể ế ằ ắ ầ ừ ố
so sánh các khóa trên t ng node đ đi vào nhánh phù h p. Các node trong ừ ể ợ
ch a các ph n t ch đóng vai trò là các khóa trung gian đ tìm ki m.ứ ầ ử ỉ ể ế
Chúng ta có th hình dung vể ề B+tree theo cách khác nh sau:ư
Có 1 t p các ph n t đã đ c s p x p th ậ ầ ử ượ ắ ế ứ
tự [1,2,3,4,5,6,7,8,9,10,11,12]
Tách t p này thành các kh i 2 ph n t , liên k t nhau theo ki u ậ ố ầ ử ế ể
linkedlist (1,2)->(3,4)->(5,6)->(7,8)->(9,10)->(11,12)
T kh i th 2 tr đi ch n ra ph n t đ u tiên làm đ i di n ta có t p ừ ố ứ ở ọ ầ ử ầ ạ ệ ậ
các ph n t t ng th 2ầ ử ở ầ ứ [3,5,7,9,11]
đây ta có c u trúc d ng cây v i 1 nút g c ch a 5 khóa (g i là key) và 6 Ở ấ ạ ớ ố ứ ọ
nút con m i nút ch a 2 ph n t có tính ch t k p gi a.ỗ ứ ầ ử ấ ẹ ữ
(3,5,7,9,11)
(1,2)->(3,4)->(5,6)->(7,8)->(9,10)->(11,12)
Khi tìm ki m trên c u trúc này ta s b t đ u t node trên tìm ki m tu n t ế ấ ẽ ắ ầ ừ ế ầ ự
đ tìm ra nhánh ch a ph n t c n tìm. D th y v i m i phép so sánh mà ể ứ ầ ử ầ ễ ấ ớ ỗ
ch a tìm ra, ta s lo i đ c 1 nhánh v i nhi u ph n t mà trong tr ng ư ẽ ạ ượ ớ ề ầ ử ườ
h p này là 2. Ti p t c l p l i thao tác v i t ng th 2 ta có t ng th 3:ợ ế ụ ặ ạ ớ ầ ứ ầ ứ
(7,11)
(3,5) (7,9) (11)
(1,2)->(3,4)->(5,6)->(7,8)->(9,10)->(11,12)
T ng t m i phép so sánh t ng 3 cho phép lo i 2 ph n t t ng 2 ươ ự ỗ ở ầ ạ ầ ử ở ầ
t ng ng 4 ph n t t ng d i cùng (t ng c n tìm ki m). T p t t c các ươ ứ ầ ử ầ ướ ầ ầ ế ậ ấ ả
node d i cùng g i là lá (leaf) chính là t p các ph n t mà ta có ban đ u. ướ ọ ậ ầ ử ầ
V i s l ng ph n t nhi u h n b t kỳ ta có th làm các thao tác trên l p ớ ố ượ ầ ử ề ơ ấ ể ặ
l i cho đ n khi còn 1 node trên cùng v i 2 ph n t . Đây chính là c u trúc dạ ế ớ ầ ử ấ ữ
li u B+tree v i b c là 3.ệ ớ ậ
Đ ph c t p tính toán c a B+treeộ ứ ạ ủ
Kích th c node là các giá tr dao đ ng trong 1 kho ng nh (vd: 1->2, 2->3) ướ ị ộ ả ỏ
xác đ nh đ i di n b i giá trị ạ ệ ở ị order (d ch là b c) c a B+tree. Đ ph c t p ị ậ ủ ộ ứ ạ
trong tìm ki m đ c tính b i s phép so sánh mà ta ph i làm (trong tr ng ế ượ ở ố ả ườ
h p x u nh t) đ đi đ n v trí c n tìm đó là:ợ ấ ấ ể ế ị ầ
Kích th c node (đ i di n b i order) * Đ cao cây (h)ướ ạ ệ ở ộ
V iớ order là 1 constant đ c xác đ nh t tr c và đ cao h là bi n s t l ượ ị ừ ướ ộ ế ố ỉ ệ
thu n v i kích th c t p ví d v i kích th c m i node là 2 có th coi ậ ớ ướ ậ ụ ớ ướ ỗ ể
như h = log n thì nh v y ta có đ ph c t p tính toán đ t đ c trong tìm ư ậ ộ ứ ạ ạ ượ
ki m làế O(log n), đây là hi u suât t t h n r t nhi u so v iệ ố ơ ấ ề ớ O(n).
Khi đã tìm đ c v trí thì chi phí cho thao tác insert hay delete trong ph m vi ượ ị ạ
1 node (các ph n t l u trong 1 node b i c u trúc m ng) là không đáng k ầ ử ư ở ấ ả ể
vì kích th c node là 1 h ng s nh (đ i di n b i order).ướ ằ ố ỏ ạ ệ ở
Ti p theo sau khi đã modify (insert ho c delete) B+tree này chúng ta ph i ế ặ ả
duy trì tính ch t c a tree vàấ ủ s cân b ngự ằ đ đ m b o tính đúng đ n và hi uể ả ả ắ ệ
qu , đ ph c t p cho các thao tác này v n làả ộ ứ ạ ẫ O(log n). Chúng ta hãy cùng đi
vào cài đ t c th .ặ ụ ể
có thể bạn quan tâm
Luận văn: Thuật toán Microsoft Decision Tree- ứng dụng của nó trong cô...
89
1.155
322
Kỹ thuật
89
(New)
Mở rộng hệ thống cổng thanh toán trực tuyến để dùng trong trường ĐHBK...
95
785
363
Kinh tế - Thương mại
95
(New)
Các kỹ thuật bảo trì khung nhìn của kho dữ liệu và đánh giá được không...
23
800
303
Thạc sĩ cao học
23
(New)
Cấu trúc dữ liệu và giải các thuật toán
229
756
275
Cơ sở dữ liệu
229
(New)
Luận văn: khái niệm, tính chất và cấu trúc vật liệu xây dựng
201
727
438
Kỹ thuật
201
(New)
Hạch toán chi phí nguyên vật liệu trực tiếp để tính giá thành sản phẩm...
2
783
290
Kế toán, kiểm toán
2
(New)
Luận văn thạc sĩ khoa học máy tính: Các phương pháp dùng trong trích c...
27
914
571
Thạc sĩ cao học
27
(New)
Tóm tắt luận án thạc sĩ: Tổng quan các phương pháp khai thác dữ liệu,...
19
950
382
Thạc sĩ cao học
19
(New)
thông tin tài liệu
Giới thiệu 1 cấu trúc dữ liệu giải thuật là BTree mà cụ thể hơn là B+Tree và ứng dụng của nó trong việc giải quyết 1 bài toán
Mở rộng để xem thêm
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
×
