Băm trong DBMS: Kỹ thuật băm tĩnh và động

Băm trong DBMS là gì?

Trong hệ quản trị cơ sở dữ liệu (DBMS), băm là một kỹ thuật để tìm kiếm trực tiếp vị trí của dữ liệu mong muốn trên đĩa mà không cần sử dụng cấu trúc chỉ mục. Phương pháp băm được sử dụng để lập chỉ mục và truy xuất các mục trong cơ sở dữ liệu, vì việc tìm kiếm một mục cụ thể bằng khóa băm ngắn hơn sẽ nhanh hơn so với việc sử dụng giá trị gốc của nó. Dữ liệu được lưu trữ dưới dạng các khối dữ liệu có địa chỉ được tạo ra bằng cách áp dụng một hàm băm; vị trí bộ nhớ nơi lưu trữ các bản ghi này được gọi là vùng nhớ. khối dữ liệu hoặc thùng dữ liệu.

Tại sao chúng ta cần hàm băm?

Dưới đây là các trường hợp trong hệ quản trị cơ sở dữ liệu (DBMS) mà bạn cần áp dụng phương pháp băm:

• Đối với cấu trúc cơ sở dữ liệu khổng lồ, việc tìm kiếm tất cả các giá trị chỉ mục qua tất cả các cấp độ và sau đó truy cập vào khối dữ liệu đích để lấy dữ liệu mong muốn là rất khó khăn.
• Hàm băm được sử dụng để lập chỉ mục và truy xuất các mục trong cơ sở dữ liệu, vì việc tìm kiếm một mục cụ thể bằng khóa băm ngắn hơn sẽ nhanh hơn so với việc sử dụng giá trị gốc.
• Hàm băm là một phương pháp lý tưởng để tính toán vị trí chính xác của một bản ghi dữ liệu trên đĩa mà không cần sử dụng cấu trúc chỉ mục.
• Nó cũng là một kỹ thuật hữu ích để thực hiện từ điển.

Các thuật ngữ quan trọng trong băm

Dưới đây là một số thuật ngữ quan trọng được sử dụng trong hàm băm:

• Thùng chứa dữ liệu: Các "thùng dữ liệu" là các vị trí trong bộ nhớ nơi lưu trữ các bản ghi. Nó cũng được biết đến như một đơn vị lưu trữ.
• Chính: a Khóa DBMS là một thuộc tính hoặc tập hợp các thuộc tính giúp bạn xác định một hàng (bộ dữ liệu) trong một quan hệ (bảng).
• Hàm băm: Bản đồping Chức năng này ánh xạ toàn bộ tập hợp các từ khóa tìm kiếm đến địa chỉ nơi lưu trữ các bản ghi thực tế.
• Đo bằng đầu dò tuyến tính: Khoảng thời gian cố định giữa các lần dò tìm. Trong phương pháp này, khối dữ liệu khả dụng tiếp theo được sử dụng để nhập bản ghi mới, thay vì ghi đè lên bản ghi cũ.
• Phương pháp thăm dò bậc hai: Giúp xác định địa chỉ thùng chứa mới bằng cách cộng kết quả đầu ra liên tiếp của một đa thức bậc hai vào giá trị ban đầu được đưa ra bởi phép tính ban đầu.
• Chỉ mục băm: Địa chỉ của khối dữ liệu. Hàm băm có thể là một hàm toán học đơn giản hoặc một hàm phức tạp.
• Double Băm: Một phương pháp được sử dụng trong bảng băm để giải quyết xung đột bằng cách áp dụng hàm băm thứ hai.
• Thùng chứa bị tràn: Tình trạng tràn bộ nhớ đệm được gọi là xung đột. Đây là giai đoạn gây tử vong cho bất kỳ hàm băm tĩnh nào.

Các loại kỹ thuật băm

Trong hệ quản trị cơ sở dữ liệu (DBMS), chủ yếu có hai loại kỹ thuật băm:

1. Băm tĩnh
2. Băm động

Hai phương pháp này khác nhau chủ yếu ở việc số lượng thùng chứa có cố định hay không, như hai phần tiếp theo sẽ giải thích.

Băm tĩnh

Trong băm tĩnh, địa chỉ thùng dữ liệu kết quả sẽ luôn giữ nguyên.

Do đó, nếu bạn tạo một địa chỉ cho, chẳng hạn, Sinh viên_ID = 10 sử dụng hàm băm mod(3), địa chỉ nhóm kết quả sẽ luôn là 1Vì vậy, bạn sẽ không thấy bất kỳ thay đổi nào về địa chỉ bucket.

Do đó, trong phương pháp băm tĩnh, số lượng thùng dữ liệu trong bộ nhớ luôn không đổi.

Hàm băm tĩnh

• Chèn một bản ghi: Khi cần chèn một bản ghi mới vào bảng, bạn tạo một địa chỉ cho bản ghi đó bằng cách sử dụng khóa băm của nó. Sau khi địa chỉ được tạo, bản ghi sẽ được lưu trữ tại vị trí đó.
• Đang tìm kiếm: Khi cần truy xuất bản ghi, hàm băm tương tự được sử dụng để truy xuất địa chỉ của bucket nơi dữ liệu được lưu trữ.
• Xóa bản ghi: Sử dụng hàm băm, trước tiên bạn lấy bản ghi cần xóa, sau đó xóa bản ghi đó khỏi địa chỉ bộ nhớ tương ứng.

Băm tĩnh được chia nhỏ hơn nữa thành:

1. Băm mở
2. Băm kín

Băm mở

Trong phương pháp băm mở, thay vì ghi đè lên bản ghi cũ hơn, khối dữ liệu khả dụng tiếp theo được sử dụng để ghi vào bản ghi mới. Phương pháp này còn được gọi là dò tuyến tính.

Ví dụ, A2 là một bản ghi mới mà bạn muốn chèn. Hàm băm tạo ra địa chỉ 222, nhưng địa chỉ này đã được sử dụng bởi một giá trị khác. Đó là lý do tại sao hệ thống tìm kiếm vùng dữ liệu tiếp theo, 501, và gán A2 cho vùng dữ liệu đó.

Băm kín

Trong phương pháp băm kín, khi các ngăn chứa đầy, một ngăn chứa mới sẽ được cấp phát cho cùng một giá trị băm và kết quả được liên kết sau kết quả trước đó.

Băm động

Băm động cung cấp một cơ chế trong đó các nhóm dữ liệu được thêm và xóa một cách linh hoạt và theo yêu cầu. Trong phương pháp băm này, hàm băm giúp bạn tạo ra một số lượng lớn giá trị, và cấu trúc sẽ mở rộng hoặc thu hẹp theo dữ liệu. Điều này làm cho nó rất phù hợp với các bảng có kích thước không thể dự đoán trước, nơi mà băm tĩnh sẽ lãng phí không gian hoặc gây tràn bộ nhớ.

Sự khác biệt giữa lập chỉ mục có thứ tự và băm

Dưới đây là những điểm khác biệt chính giữa lập chỉ mục và băm:

Tóm lại, hãy chọn theo thứ tự. lập chỉ mục Dùng cho các truy vấn phạm vi và băm để tìm kiếm chính xác kết quả khớp với khóa.

Va chạm là gì?

Xung đột băm (hash collision) là tình trạng mà các giá trị băm thu được từ hai hoặc nhiều mục trong tập dữ liệu ánh xạ sai đến cùng một vị trí trong tập dữ liệu gốc. bảng băm.

Cách xử lý xung đột băm (Hashing Collision)

Có hai kỹ thuật bạn có thể sử dụng để tránh xung đột hàm băm:

1. Tóm lại: Phương pháp này sử dụng một hàm băm thứ cấp, được áp dụng liên tục cho đến khi tìm thấy một vị trí trống để đặt bản ghi.
2. Chuỗi: Phương pháp liên kết chuỗi xây dựng một danh sách liên kết các mục có khóa băm ra cùng một giá trị. Phương pháp này yêu cầu thêm một trường liên kết ở mỗi vị trí trong bảng.

Câu Hỏi Thường Gặp