Bài viết sưu tầm

Tổ chức tệp băm trên cơ sở dữ liệu

Trước khi trình bày tệp băm cần nhắc lại một vài nét về khái niệm hàm băm (Hasded Function). Nếu mỗi bản ghi đều có một khóa là giá trị số (ví dụ x), hàm băm h(x) (đối số là x) nhận một giá trị trong khoảng [0,k] với k là một giá trị nguyên dương nào đó (thường thấy k là một số nguyên tố), i là địa chỉ băm của cụm. Khi đó h(x) = i mod k.

Tư tưởng cơ bản của tổ chức tệp băm là phân chia tập hợp các bản ghi của tệp dữ liệu thành các cụm (buckets). Mỗi cụm bao gồm một hay nhiều khối (block). Mỗi khối chứa một số lượng cố định các bản ghi.

Mỗi cụm ứng với một địa chỉ băm. Địa chỉ băm được đánh số từ 0 đến k – 1. Ở đầu mỗi khối đều chứa con trỏ, mỗi con trỏ ứng với một cụm, đó là địa chỉ của khối đầu tiên trong cụm.

Tổ chức tệp băm k cụm như sau:

Cụm 0 có 02 khối ghi b1,b2. Khối b2 có con trỏ  rỗng “null”. Cụm 1 chỉ có một khối b3 và có  con trỏ rỗng. Cụm k – 1 có 03 khối b4, b5, b6.

(Xem fie đính kèm để thấy hình minh họa)