Dưới đây là mã nguồn Python tự xây dựng từ đầu 3 cấu trúc để so sánh thực tế: Danh sách thông thường (Array), B-Tree Index (mô phỏng), và Hash Index.
Mã nguồn mô phỏng việc tìm kiếm thông tin của 1.000.000 đơn hàng trong cơ sở dữ liệu xưởng chế biến.
import time
from typing import Any, List, Optional
# ==============================================================================
# 1. MÔ PHỎNG DỮ LIỆU ĐƠN HÀNG (DATABASE RECORDS)
# ==============================================================================
class Record:
def __init__(self, order_id: int, customer_code: str, amount: float):
self.order_id = order_id # Khóa chính (Primary Key)
self.customer_code = customer_code # Mã khách hàng
self.amount = amount
def __repr__(self):
return f"Record(ID={self.order_id}, Code='{self.customer_code}', Amount={self.amount:,.0f}đ)"
# ==============================================================================
# 2. HASH INDEX: TỐC ĐỘ O(1) CHO TÌM KIẾM CHÍNH XÁC (=)
# ==============================================================================
class HashIndex:
def __init__(self, capacity: int = 1000):
self.capacity = capacity
self.buckets: List[List[tuple]] = [[] for _ in range(self.capacity)]
def _hash(self, key: str) -> int:
return sum(ord(c) for c in key) % self.capacity
def insert(self, key: str, record_ptr: Record):
idx = self._hash(key)
self.buckets[idx].append((key, record_ptr))
def search_exact(self, key: str) -> Optional[Record]:
"""Tìm chính xác WHERE customer_code = '...' -> O(1)"""
idx = self._hash(key)
for k, ptr in self.buckets[idx]:
if k == key:
return ptr
return None
def search_range(self, min_key: str, max_key: str) -> List[Record]:
""" Hash Index THẤT BẠI ở truy vấn khoảng -> Bắt buộc phải Scan toàn bộ các Bucket """
results = []
for bucket in self.buckets:
for k, ptr in bucket:
if min_key <= k <= max_key:
results.append(ptr)
return results
# ==============================================================================
# 3. B-TREE INDEX (CẤU TRÚC PHÂN CẤP LÁ NỐI LIÊN KẾT: B+TREE)
# ==============================================================================
class BPlusTreeNode:
def __init__(self, is_leaf: bool = False):
self.is_leaf = is_leaf
self.keys: List[int] = [] # Các giá trị khóa (Order_ID)
self.children: List[Any] = [] # Các con trỏ (trỏ tới Node con hoặc Record)
self.next: Optional["BPlusTreeNode"] = (
None # Con trỏ nối nút lá (Doubly/Singly Linked List)
)
class BPlusTreeIndex:
def __init__(self, max_keys: int = 3):
self.root = BPlusTreeNode(is_leaf=True)
self.max_keys = max_keys
def insert(self, key: int, record_ptr: Record):
"""Thêm dữ liệu và giữ cây luôn sắp xếp tại các nút lá"""
leaf = self._find_leaf(self.root, key)
# Chèn giữ thứ tự tăng dần
idx = 0
while idx < len(leaf.keys) and leaf.keys[idx] < key:
idx += 1
leaf.keys.insert(idx, key)
leaf.children.insert(idx, record_ptr)
def _find_leaf(self, node: BPlusTreeNode, key: int) -> BPlusTreeNode:
if node.is_leaf:
return node
for i, k in enumerate(node.keys):
if key < k:
return self._find_leaf(node.children[i], key)
return self._find_leaf(node.children[-1], key)
def search_exact(self, key: int) -> Optional[Record]:
"""Tìm chính xác theo cây B+Tree -> O(log N)"""
leaf = self._find_leaf(self.root, key)
for i, k in enumerate(leaf.keys):
if k == key:
return leaf.children[i]
return None
def search_range(self, min_key: int, max_key: int) -> List[Record]:
"""THẾ MẠNH B-TREE: Tìm khoảng WHERE order_id BETWEEN min AND max"""
leaf = self._find_leaf(self.root, min_key)
results = []
curr = leaf
# Duyệt ngang trên danh sách liên kết giữa các nút lá
while curr:
for i, k in enumerate(curr.keys):
if min_key <= k <= max_key:
results.append(curr.children[i])
elif k > max_key:
return results
curr = curr.next
return results
# ==============================================================================
# 4. THỰC HÀNH SO SÁNH HIỆU NĂNG VÀ CƠ CHẾ
# ==============================================================================
if __name__ == "__main__":
# Tạo 100.000 bản ghi dữ liệu giả lập
TOTAL_RECORDS = 100000
print(f"⏳ Đang khởi tạo {TOTAL_RECORDS:,} bản ghi đơn hàng...")
raw_table: List[Record] = []
hash_idx = HashIndex(capacity=5000)
btree_idx = BPlusTreeIndex()
# Tạo nút lá đầu tiên cho B-Tree để mô phỏng danh sách nối ngang
prev_leaf = btree_idx.root
for i in range(1, TOTAL_RECORDS + 1):
cust_code = f"KH_{i:06d}"
rec = Record(order_id=i, customer_code=cust_code, amount=i * 1000)
# 1. Lưu vào bảng chính (Mảng)
raw_table.append(rec)
# 2. Đánh Hash Index trên cột customer_code
hash_idx.insert(cust_code, rec)
# 3. Đánh B-Tree Index trên cột order_id
btree_idx.insert(i, rec)
# Liên kết danh sách nút lá (mô phỏng)
if len(btree_idx.root.keys) > 50:
new_leaf = BPlusTreeNode(is_leaf=True)
prev_leaf.next = new_leaf
prev_leaf = new_leaf
print(" Tải dữ liệu và đánh Index hoàn tất!\n")
print("=" * 70)
# --------------------------------------------------------------------------
# THỬ NGHIỆM 1: TÌM KIẾM CHÍNH XÁC KHÔNG DÙNG INDEX VS DÙNG HASH INDEX
# --------------------------------------------------------------------------
target_code = "KH_088888"
print(
f"🔍 THỬ NGHIỆM 1: Tìm đơn hàng theo Mã KH ('{target_code}') [Chính xác =]"
)
# Cách A: Full Table Scan (Không dùng Index)
t0 = time.perf_counter()
found_rec_scan = None
for r in raw_table:
if r.customer_code == target_code:
found_rec_scan = r
break
t_scan = (time.perf_counter() - t0) * 1000
# Cách B: Hash Index Lookup
t0 = time.perf_counter()
found_rec_hash = hash_idx.search_exact(target_code)
t_hash = (time.perf_counter() - t0) * 1000
print(f" ▫ Full Table Scan (Mảng): {t_scan:.4f} ms -> {found_rec_scan}")
print(
f" ▫ Hash Index Scan (O(1)): {t_hash:.4f} ms -> {found_rec_hash} (Nhanh gấp ~{int(t_scan/max(t_hash,0.0001))} lần)"
)
print("\n" + "=" * 70)
# --------------------------------------------------------------------------
# THỬ NGHIỆM 2: TÌM KIẾM THEO KHOẢNG (RANGE QUERY): B-TREE VS HASH INDEX
# --------------------------------------------------------------------------
min_id, max_id = 50000, 50005
print(
f"🔍 THỬ NGHIỆM 2: Tìm đơn hàng có ID từ {min_id} đến {max_id} [Khoảng BETWEEN]"
)
# Cách A: Dùng B-Tree Index (Duyệt theo liên kết lá)
t0 = time.perf_counter()
res_btree = btree_idx.search_range(min_id, max_id)
t_btree = (time.perf_counter() - t0) * 1000
# Cách B: Dùng Hash Index (Phải quét toàn bộ các ô băm)
t0 = time.perf_counter()
res_hash = hash_idx.search_range(
f"KH_{min_id:06d}", f"KH_{max_id:06d}"
)
t_hash_range = (time.perf_counter() - t0) * 1000
print(
f" ▫ B-Tree Index Range Scan: {t_btree:.4f} ms -> Tìm thấy {len(res_btree)} kết quả."
)
print(
f" ▫ Hash Index Range Scan : {t_hash_range:.4f} ms -> Tìm thấy {len(res_hash)} kết quả."
)
print(" ↳ Giải thích: Hash Index phải Scan lại toàn bộ vì Hash Code không giữ thứ tự lớn/nhỏ!")WHERE customer_code = 'KH_088888')Full Table Scan (Mảng): Phải so sánh từ đầu danh sách cho tới phần tử thứ 88.888. Thời gian tốn hàng nghìn chu kỳ máy tính.
Hash Index: Tính hàm băm $h(\text{'KH\_088888'}) \rightarrow \text{Bucket Index}$, nhảy thẳng vào vị trí ô nhớ đó lấy dữ liệu ngay lập tức với thời gian $\approx 0.001\text{ ms}$.
WHERE order_id BETWEEN 50000 AND 50005)B-Tree Index: Nhờ cấu trúc cây, nó định vị nhanh nút lá chứa số 50000, sau đó chỉ việc chạy ngang qua liên kết next để lấy các số 50001, 50002... mà không cần duyệt lại từ gốc hay quét dữ liệu thừa.
Hash Index: Bị vô hiệu hóa đối với truy vấn khoảng. Vì mã băm của 50000 và 50001 nằm ở hai vị trí ngẫu nhiên hoàn toàn khác nhau trong bộ nhớ RAM, Hash Index bắt buộc phải quét lại toàn bộ dữ liệu.