B-Tree
1. Giới thiệu
B-Tree là một cấu trúc dữ liệu cây tự cân bằng được thiết kế đặc biệt cho hệ thống lưu trữ. Nó cho phép tìm kiếm, chèn, xóa trong thời gian logarit và rất hiệu quả với dữ liệu lớn được lưu trên đĩa.
2. Đặc điểm chính
- Mỗi node có thể chứa nhiều khóa
- Các khóa trong node được sắp xếp tăng dần
- Mỗi node có số lượng con nằm trong khoảng cho phép
- Tất cả leaf node đều ở cùng một mức
- Phù hợp với hệ thống lưu trữ ngoài (disk-based storage)
3. Implementation
public class BTree<K extends Comparable<K>, V> {
private static final int M = 4; // Bậc của B-tree
private static class Node {
private int n; // Số lượng khóa hiện tại
private Entry[] entries = new Entry[M-1]; // Mảng các entry
private Node[] children = new Node[M]; // Mảng các node con
private boolean leaf = true; // Có phải node lá không
private Node(int n) {
this.n = n;
}
}
private static class Entry {
private Comparable key;
private Object value;
private Node next;
public Entry(Comparable key, Object value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private Node root;
private int height;
private int n;
public BTree() {
root = new Node(0);
}
// Tìm kiếm giá trị theo khóa
public V search(K key) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
return search(root, key, height);
}
private V search(Node x, K key, int ht) {
Entry[] entries = x.entries;
// Node lá
if (ht == 0) {
for (int j = 0; j < x.n; j++) {
if (eq(key, entries[j].key)) return (V) entries[j].value;
}
}
// Node trong
else {
for (int j = 0; j < x.n; j++) {
if (j+1 == x.n || less(key, entries[j+1].key))
return search(entries[j].next, key, ht-1);
}
}
return null;
}
// Chèn một cặp key-value
public void insert(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
Node u = insert(root, key, value, height);
n++;
if (u == null) return;
// Cần tạo root mới
Node t = new Node(2);
t.entries[0] = new Entry(root.entries[0].key, null, root);
t.entries[1] = new Entry(u.entries[0].key, null, u);
root = t;
height++;
}
private Node insert(Node h, K key, V value, int ht) {
int j;
Entry t = new Entry(key, value, null);
// Node lá
if (ht == 0) {
for (j = 0; j < h.n; j++) {
if (less(key, h.entries[j].key)) break;
}
}
// Node trong
else {
for (j = 0; j < h.n; j++) {
if ((j+1 == h.n) || less(key, h.entries[j+1].key)) {
Node u = insert(h.entries[j++].next, key, value, ht-1);
if (u == null) return null;
t.key = u.entries[0].key;
t.value = null;
t.next = u;
break;
}
}
}
for (int i = h.n; i > j; i--)
h.entries[i] = h.entries[i-1];
h.entries[j] = t;
h.n++;
if (h.n < M) return null;
else return split(h);
}
// Tách node khi đầy
private Node split(Node h) {
Node t = new Node(M/2);
h.n = M/2;
for (int j = 0; j < M/2; j++)
t.entries[j] = h.entries[M/2 + j];
return t;
}
// So sánh hai khóa
private boolean less(Comparable k1, Comparable k2) {
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2) {
return k1.compareTo(k2) == 0;
}
}
4. Ví dụ sử dụng
public class BTreeExample {
public static void main(String[] args) {
BTree<Integer, String> tree = new BTree<>();
// Chèn các cặp key-value
tree.insert(1, "One");
tree.insert(2, "Two");
tree.insert(3, "Three");
tree.insert(4, "Four");
tree.insert(5, "Five");
// Tìm kiếm
System.out.println("Value for key 3: " + tree.search(3)); // "Three"
System.out.println("Value for key 6: " + tree.search(6)); // null
}
}
5. Độ phức tạp
- Tìm kiếm: O(log n)
- Chèn: O(log n)
- Xóa: O(log n)
- Không gian: O(n)
6. Ứng dụng thực tế
- Hệ quản trị cơ sở dữ liệu (Database Management Systems)
- Hệ thống file
- Indexing trong cơ sở dữ liệu
- Lưu trữ dữ liệu trên đĩa
- Hệ thống cache
7. So sánh với B+ Tree
- B+ Tree lưu trữ dữ liệu chỉ ở leaf nodes
- B+ Tree có các leaf nodes được liên kết với nhau
- B+ Tree thường hiệu quả hơn cho range queries
- B Tree tốt hơn cho việc tìm kiếm một giá trị cụ thể
8. Bài tập thực hành
- Implement thao tác xóa
- Thêm hỗ trợ cho range queries
- Tối ưu hóa việc đọc/ghi đĩa
- Implement iterator
- Thêm các operation như findMin, findMax