Bài giảng Nhập môn cơ sở dữ liệu - Bài 5: Tổ chức dữ liệu vật lý

Tổ chức dữ li

ệ

u v

ậ

t l

ý

Vũ Tuyết Trinh

[email protected]n

Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin

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

Hệ

Ứng dụng

CSDL

Hệ QTCSDL

CSDL

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Bộ xử lý

câu hỏi

Bộ quản lý

Giao dịch

Bộ quản lý

lưu trữ

Quản lý lưu trữ

{ Tổ chức tệp: sắp xếp các

bản ghi trên thiết bị nhớ

ngoài

Bộ quản lý lưu trữ

Quản lý buffer

Quản

lý

giao

dịch

z RID (record id): xác định địa

chỉ vật lý của các bản ghi

z chỉ số: cấu trúc dữ liệu xác

định sự tương ứng giữa

RID của bản ghi và giá trị

của trường (khoá)

Quản lý tệp

{ Vùng nhớ đệm: trung gian

giữa thiết bị nhớ ngoài và

bộ nhớ trong (có thể sử

dụng cho cả DL và chỉ số)

Metadata &

Data dictionary

Data & index

Tổ chức bộ nhớ ngoài

{ Mục đích: giảm thiểu truy xuất đến dữ liệu

không cần thiết trên thiết bị nhớ ngoài

{ Các vấn đề cần quan tâm

z Cấu trúc lưu trữ

z Các phép toán (thêm, xoá, sửa, tìm kiếm)

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Các thiết bị nhớ ngoài

{ Đĩa từ, băng từ, trống từ, ...

{ Đĩa từ: được tổ chức thành từng trang

z Chí phí truy nhập đến các trang bất kỳ là tương

đương

z Chí phí đọc nhiều trang liền nhau < chí phí đọc các

trang đó theo thứ tự bất kỳ

{

B

ă

ng t

ừ

:

z chỉ có thể đọc được các trang liền nhau

z rẻ hơn đĩa từ nhưng chi phí truy nhập thương lớn hơn

{ ...

Đĩa từ vs. bộ nhớ trong

{ Tốc độ truy nhập bộ

ms vs. ns (~1000 lần)

{ Kích thước

GB vs. 10x MB (~ 100 lần với cùng chi phí)

{ Lưu trữ

ổn định (kể cả khi mất điện) vs. tạm thời

{ Phân chia block

4KB vs. 1Byte

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Nội dung

9 Tổng quan về tổ chức bộ nhớ ngoài

{ Tổ chức tệp đống

{ Tổ chức tệp băm

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

{ Cây cân bằng

Tổ chức tệp đống (Heap File)

{ Lưu trữ kế tiếp các bản ghi trong các trang

không tuân theo mộ

t th

ứ

t

ự đặ

c bi

ệt nào

{ Để thực hiện các phép toán, cần:

z Ghi nhớ số trang trong 1 tệp

z Ghi nhớ không gian trống trên các trang

z Ghi nhớ các bản ghi trên các trang

¾ Có các con trỏ trỏ tới tất cả các trang của tệp và

các con trỏ này được lưu trữ ở bộ nhớ trong.

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Cài đặt tệp đống bằng danh sách

Data

Full Pages

Page

Header

Page

Data

Pages with

Free Space

Page

{ Cần lưu trữ HeaderPage và tên của tệp

{ Mỗi trang gồm dữ liệu và 2 con trỏ

Các phép toán

{ Tìm kiếm 1 bản ghi

{ Thêm 1 bản ghi

{ Xoá 1 bản ghi

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

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Sử dụng trang danh bạ

Data

Page 1

Header

Page

Data

Page 2

Data

Page N

DIRECTORY

{ Lưu thông tin về số byte còn trống trên trang đó

{ Danh bạ là 1 tập các trang

Tổ chức tệp băm (Hash File)

{ Mục đích

z Sử dụng chỉ số để hạn chế số lượng phép truy xuất

đĩa bằng các phân nhóm các bản ghi (giả thiết n

nhóm)

z Mapping giá trị khoá với vị trí của (nhóm) bản ghi

tương ứng

{

D

ự

a trên b

ả

ng b

ă

m (

hash table

)

z Hàm băm (hash function)

z Cụm (bucket)

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Ví dụ

h(x) = x mod 4

1

2

4

3

Store

hash

1

2

3

4

2

3

Ví dụ tiếp

h(x) = x mod 4

Store

hash

10

12

6

1

2

3

4

2

3

4

10

12

6

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Các phép toán

{ Tìm kiếm 1 bản ghi

{ Thêm 1 bản ghi

{ Xoá 1 bản ghi

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

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)

{ Hạn chế việc sử dụng nhiều trang bộ nhớ cho 1

cụm

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Tổ chức tệp chỉ dẫn (Index File)

{ Tệp chỉ dẫn theo khoá được chọn trong bản ghi

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

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

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

{ Tệp chỉ dẫn được sắp xếp theo giá trị của khoá.

Các phép toán

{ Tìm kiếm 1 bản ghi

{ Thêm 1 bản ghi

{ Xoá 1 bản ghi

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

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Tìm kiếm 1 bản ghi

{ Tìm kiếm tuần tự

z Duyệt tệp chỉ dẫn từ bản ghi đầu tiên đến khi tìm thấy

bản ghi có khoá k cần tìm

z Nhận xét

{ chậm đối với các tệp chỉ dẫn nói chung.

{ Thích hợp với các tệp chỉ dẫn nhỏ đủ để lưu ở bộ

nhớ trong

{ Tìm kiếm nhị phân

z Chia đôi tệp chỉ dẫn đã sắp xếp để hạn chế số bản

ghi cần duyệt

z Tại mỗi lần chia hạn chế được ½ số bản ghi cần xem

xét

Cây cân bằng (BalanceTree)

{ B-tree cân bằng được tổ chức theo cấp m, có

các tính chất sau đây:

z Gốc của cây hoặc là một nút lá hoặc ít nhất có hai

con.

z Mỗi nút (trừ nút gốc và nút lá) có từ [m/2] đến m con.

z Mỗi đường đi từ nút gốc đến bất kỳ nút lá nào đều có

độ dài như nhau.

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Ví dụ

Nhận xét

{ Cấu trúc của mỗi nút trong B-tree

(p0, kl, p1, k2,...,kn, pn)

z pi (i=l..n) là con trỏ trỏ tới khối i của nút có ki là khoá

đầu tiên của khối đó.

z Các khoá k trong một nút được sắp xếp theo thứ tự

tăng dần.

{ Mọi khoá trong cây con, trỏ bởi pi đều nhỏ hơn

ki+1

{ Mọi khoá trong cây con, trỏ bởi pn đều lớn hơn

kn.

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Các phép toán

{ Tìm kiếm 1 bản ghi

{ Thêm 1 bản ghi

{ Xoá 1 bản ghi

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

So sánh các cách tổ chức dữ liệu

{ Tệp đống

{ Tệp băm

{ Tệp chỉ dẫn

{ Cây cân bằng

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Kết luận

{ Truy cập đến CSDL thường liên quan đến một

ph

ầ

n nh

ỏ

các b

ả

n ghi trong m

ộ

t t

ệ

p d

ữ

li

ệ

u hay

một vài trường (đặc biệt là các trường khoá)

của các bản ghi dữ liệu.

¾ Xác định các yêu cầu này cho phép thiết kế dữ liệu

vật lý hiệu quả thông qua việc sử dụng các tổ chức

lưu trữ đặc biệt

{ Tệp chỉ dẫn được tạo lập trên khoá tìm kiếm để

tăng hiệu quả của lưu trữ dữ liệu

¾ Hiệu quả của các cấu trúc chỉ dẫn khác nhau phụ

thuộc vào điều kiện áp dụng chúng

ũ Tuyết Trinh, b/m Hệ thống thông tin,

Bài giảng Nhập môn cơ sở dữ liệu - Bài 5: Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh