Bài giảng Cơ sở dữ liệu - Chương 7: Tổ chức dữ liệu vật lý

10/11/2019

Nội dung

• 1. Mô hình tổ chức bộ nhớ

• 2. Tổ chức tệp đống

• 3. Tổ chức tệp băm

• 4. Tổ chức tệp chỉ dẫn

• 5. Cây cân bằng

Tổ chức dữ liệu vật lý

Nguyễn Hồng Phương

[email protected].vn

http://is.hust.edu.vn/~phuongnh

Bộ môn Hệ thống thông tin

Viện Công nghệ thông tin và Truyền thông

Đại học Bách Khoa Hà Nội

1

2

1. Mô hình tổ chức bộ nhớ

Bộ nhớ ngoài

• Phương tiện nhớ của máy tính hình thành

một phân cấp bộ nhớ bao gồm 2 loại chính:

• Bộ nhớ ngoài (bộ nhớ thứ cấp): đĩa từ, băng

từ,...

– Bộ nhớ sơ cấp:

• Bao gồm các thiết bị nhớ mà CPU của máy tính có thể

thao tác trực tiếp trên đó, như bộ nhớ chính, bộ nhớ đệm

cache.

• Cung cấp cơ thế truy cập dữ liệu nhanh nhưng lại bị giới

hạn về dung lượng.

– Bộ nhớ thứ cấp:

• Đĩa được chia thành các khối vật lý (sector) -

512 byte đến 4096 byte được đánh địa chỉ

khối gọi là địa chỉ tuyệt đối

• Bao gồm các đĩa từ, đĩa quang, băng từ.

• Dung lượng lớn hơn, chi phí rẻ hơn.

• Cung cấp cơ chế truy cập dữ liệu chậm hơn.

• CPU không xử lý dữ liệu trực tiếp trên bộ nhớ thứ cấp mà

dữ liệu được sao chép sang bộ nhớ sơ cấp để CPU xử lý.

• Mỗi tệp dữ liệu chiếm 1 hoặc nhiều khối

3

4

• Mỗi khối chứa 1 hoặc nhiều bản ghi

1

10/11/2019

2. Tổ chức tệp đống (Heap file)

1. Mô hình tổ chức bộ nhớ (tiếp)

• Tổ chức dữ liệu

• Thao tác với dữ liệu của tệp thông qua

địa chỉ tuyệt đối của các khối.

• Các bản ghi đều có địa chỉ:

–địa chỉ tuyệt đối của byte đầu tiên

–Bản ghi lưu trữ kế tiếp trong các khối,

không tuân theo một thứ tự đặc biệt nào.

k1 k2 k3



k4 k5 k6



k7 k8



–địa chỉ khối và số byte tính từ đầu khối

đến vị trí đầu bản ghi

• Các thao tác

–Tìm kiếm một bản ghi: tìm kiếm một bản

ghi có giá trị khóa cho trước => quét toàn

bộ tệp.

–Thêm một bản ghi: thêm bản ghi mới vào

sau bản ghi cuối cùng

• Địa chỉ của các bản ghi/khối được lưu ở

1 tệp => sử dụng con trỏ (pointer) để

truy cập dữ liệu của tệp.

5

6

2. Tổ chức tệp đống (Heap file)

• Ví dụ:

• Các thao tác (tiếp)

–Xóa một bản ghi: thao tác xóa bao hàm

thao tác tìm kiếm. Nếu có bản ghi cần xóa

thì nó sẽ được đánh dấu là xóa => hệ

thống cần tổ chức lại đĩa định kỳ.

–Sửa một bản ghi: tìm bản ghi rồi sửa một

hay nhiều trường.

Thêm

bản ghi

có giá trị

khóa là

32

Xóa bản

ghi có giá

trị khóa

là 64

7

8

2

10/11/2019

3. Tổ chức tệp băm (Hashed files)

• Hàm băm: h(x) nhận một giá trị trong

đoạn [0,k], ví dụ: h(x)=x mod k

• Tổ chức tệp dữ liệu

–Phân chia các bản ghi vào các cụm.

–Mỗi cụm gồm một hoặc nhiều khối.

–Mỗi khối chứa số lượng bản ghi cố định.

–Tổ chức lữu trữ dữ liệu trong mỗi cụm áp

dụng theo tổ chức đống

• Tiêu chí chọn hàm băm: phân bố các

bản ghi tương đối đồng đều theo các

cụm.

9

10

3. Tổ chức tệp băm (Hashed files)

h(x) = x mod 5

12

10

17

18

1

2

4

Store

hash

Store

hash

3

0

1

2

3

4

0

1

2

3

4

10

1

4

1

3

12

17

18

11

12

3

10/11/2019

3. Tổ chức tệp băm (Hashed files)

• Các thao tác

3. Tổ chức tệp băm (Hashed files)

–Xóa một bản ghi: tìm kiếm bản ghi rồi xóa

–Sửa đổi một bản ghi:

–Tìm kiếm một bản ghi: để tìm bản ghi có

khóa x, tính h(x) sẽ được cụm chứa bản

ghi, sau đó tìm kiếm theo tổ chức đống.

–Thêm một bản ghi: thêm 1 bản ghi có giá

trị khóa là x.

•nếu trường cần sửa có tham gia vào trong khóa

thì việc sửa sẽ là loại bỏ bản ghi này và thêm

mới 1 bản ghi (bản ghi có thể thuộc vào 1 cụm

khác)

•nếu trường cần sửa không thuộc khóa: tìm

kiếm rồi sửa. Nếu bản ghi không tồn tại thì

xem như có lỗi.

•nếu trong tệp đã có một bản ghi có trùng khóa

x =>bản ghi mới sai (vì khóa là duy nhất!)

•nếu không có bản ghi trùng khóa, bản ghi được

thêm vào khối còn chỗ trống đầu tiên trong

cụm, nếu hết chỗ thì tạo khối mới.

13

14

4. Tổ chức tệp chỉ dẫn(Indexed Files)

• Tìm kiếm trên tệp chỉ dẫn

• Giả sử giá trị các khóa của các bản ghi được

sắp xếp tăng dần.

–Cho một giá trị khóa k_i, tìm một bản ghi

(k_m,d) trong tệp chỉ dẫn sao cho k_m<=k_i

và:

• Tệp chỉ dẫn được tạo bằng cách chọn các giá

trị khóa trong các bản ghi

• Tệp chỉ dẫn bao gồm các cặp (k,d), trong đó

k là giá trị khoá của bản ghi đầu tiên, d là

địa chỉ của khối (hay con trỏ khối).

•hoặc (k_m,d) là bản ghi cuối cùng trong tệp chỉ

dẫn

•hoặc bản ghi tiếp theo (k_m+1,d') thỏa mãn

k_i<k_m+1

–Khi đó, chúng ta nói k_mphủ k_i

–Tìm kiếm này có thể là:

•tuần tự

•nhị phân

16

15

4

10/11/2019

4. Tổ chức tệp chỉ dẫn(Indexed Files)

• Các thao tác

–Xóa một bản ghi: giống như thêm một bản

ghi, nếu xóa mà tạo thành 1 khối rỗng, khi

đó có thể loại bỏ cả khối đó.

– Tìm kiếm một bản ghi

– Thêm một bản ghi: xác định khối i sẽ chứa bản

ghi đó

–Sửa một bản ghi:

• nếu trong khối i còn chỗ thì đặt bản ghi này vào đúng

chỗ theo thứ tự sắp xếp của khóa, dồn toa các bản ghi

đằng sau nó.

•Sử dụng thủ tục tìm kiếm để xác định bản ghi

cần sửa

• nếu khối i hết chỗ thì việc thêm này sẽ đẩy bản ghi cuối

cùng trong khối sang làm bản ghi đầu tiên của khối tiếp

theo i+1 => sửa bản ghi chỉ dẫn tương ứng

• nếu bản ghi mới này có giá trị khóa lớn hơn tất cả mọi

khóa trong tệp dữ liệu chính và không còn chỗ thì tạo

thêm một khối mới.

•nếu các trường cần sửa không phải là khóa thì

sửa bình thường

•nếu các trường cần sửa tham gia vào khóa thì

quá trình sửa sẽ là quá trình thêm và xóa 1

bản ghi.

17

18

5. Cây cân bằng(Balanced-trees)

• B-tree được tổ chức theo cấp m, có các

tính chất sau đây:

–Gốc của cây hoặc là một nút lá hoặc ít

nhất có hai con.

–Mỗi nút (trừ nút gốc và nút lá) có từ [m/2]

đến m con.

–Mỗi đường đi từ nút gốc đến bất kỳ nút lá

nào đều có độ dài như nhau.

• Cấu trúc của mỗi nút trong B-cây có dạng

(p₀, k₁, p₁, k₂,...,k_n, p_n) với p_i(i=1..n) là con

trỏ trỏ tới khối i của nút có k_ilà khoá đầu

tiên của khối đó. Các khoá k trong một nút

được sắp xếp theo thứ tự tăng dần.

19

20

5

10/11/2019

5. Cây cân bằng(Balanced-trees)

• Các thao tác

• Mọi khoá trong cây con, trỏ bởi con trỏ

p₀đều nhỏ hơn k₁;

• Mọi khoá trong cây con, trỏ bởi con trỏ

–Tìm kiếm một bản ghi: xác định đường

dẫn từ nút gốc tới nút lá chứa bản ghi này

–Thêm một bản ghi:

p_iđều nhỏ hơn k_i+1

.

•Xác định vị trí nút lá sẽ chứa bản ghi này (như

tìm kiếm)

•Nếu còn chỗ thì thêm bình thường

•Nếu hết chỗ thì phải tạo thêm nút lá mới,

chuyển nửa dữ liệu cuối của nút lá hiện tại

sang nút mới, sau đó thêm bản ghi mới này

vào vị trí phù hợp nút lá hiện tại hoặc nút mới

tạo

• Mọi khoá trong cây con, trỏ bởi con trỏ

p_nđều lớn hơn k_n.

•Rất có khả năng “động chạm” đến nút

cha,….nút gốc.

21

22

Kết luận

5. Cây cân bằng(Balanced-trees)

–Loại bỏ 1 bản ghi:

• Tổ chức tệp chỉ dẫn:

– được áp dụng phổ biến

•Dùng thủ tục tìm kiếm một bản ghi để xác định

nút L có thể chứa bản ghi đó.

•Rất có khả năng “động chạm” đến nút

cha,…,nút gốc.

– Với các ứng dụng yêu cầu cả xử lý tuần tự và truy

nhập trực tiếp đến các bản ghi

– Hiệu năng sẽ giảm khi kích thước tệp tăng =>chỉ

dẫn B-cây

• Tổ chức băm:

– Dựa trên 1 hàm băm, cho phép tìm thấy địa chỉ

khoản mục dữ liệu một cách trực tiếp

– Hàm băm tốt? Phân bố các bản ghi đồng đều

trong các cụm

23

24

6

10/11/2019

Lời hay ý đẹp

Bản chất của tình bạn chân thật là

khoan dung với những lỗi nhỏ của bạn

David Storey

25

26

7

Bài giảng Cơ sở dữ liệu - Chương 7: Tổ chức dữ liệu vật lý - Nguyễn Hồng Phương