TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BỘ MÔN CÔNG NGHỆ THÔNG TIN QUẢN TRỊ DỮ LIỆU - CT467 Chương 2: LƯU TRỮ VÀ CẤU TRÚC TẬP TIN Biên soạn: Ths. Nguyễn Thị Kim Yến Ntkyen@ctu.vn MỤC TIÊU Nhằm giới thiệu 2 kỹ thuật rất phổ biến được sử dụng để tăng hiệu suất truy cập dữ liệu trong các Hệ QT CSDL là chỉ mục (index) và băm (hash) 1 6. Chỉ mục và băm Chỉ mục Băm Chỉ mục Băm tĩnh được sắp Chỉ mục Băm B+-cây động 2 6.1 Chỉ mục (indexing) • Chỉ mục: một cấu trúc dữ liệu được dùng để định vị và truy cập nhanh nhất vào trong các bảng DB • Một Index là một con trỏ tới dữ liệu trong một bảng Tăng tốc độ tìm kiếm và truy cập DB 3 6.1 Chỉ mục (indexing) (tt) • Cấu trúc của Index: Chứa con trỏ trỏ đến địa Chứa bản sao các chỉ của bản ghi có giá trị giá trị của cột được cột index tương ứng tạo Index 4 6.1 Chỉ mục được sắp (Ordered index) • Là chỉ mục lưu trữ các giá trị khoá tìm kiếm trong thứ tự được sắp và kết hợp từng khoá tìm kiếm với các mẫu tin chứa khoá tìm kiếm này 5 6.1 Chỉ mục được sắp (Ordered index) (tt) • Nếu file chứa các mẩu tin được sắp tuần tự theo khóa tìm kiếm, chỉ mục theo khoá tìm kiếm này được gọi là chỉ mục sơ cấp (hay chỉ mục theo cụm) • Nếu file chứa các mẩu tin không được sắp theo khóa tìm kiếm, chỉ mục theo khóa tìm kiếm này được gọi là chỉ mục thứ cấp (hay chỉ mục không phân cụm) 6 a) Chỉ mục sơ cấp (Primary index) • Chỉ mục đặc (dense index): có mẩu tin chỉ mục cho mỗi khóa tìm kiếm Brighton A-217 750 Downtown A-101 500 Brighton Downtown A-110 600 Downtown Mianus A-215 700 Mianus Perryridge A-102 400 Perryridge Perryridge A-201 900 Redwood Perryridge A-218 700 Round Hill Redwood A-222 700 Round Hill A-305 350 • 7 a) Chỉ mục sơ cấp (Primary index) (tt) • Chỉ mục thưa (sparse index): chỉ có mẩu tin chỉ mục cho một số khóa tìm kiếm Brighton A-217 750 Downtown A-101 500 Brighton Downtown A-110 600 Mianus Mianus A-215 700 Redwood Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 700 Round Hill A-305 350 • 8 b) Chỉ mục thứ cấp (Secondary index) • Mỗi index record trỏ tới một bucket chứa các con trỏ tới tất cả các bản ghi có giá trị search-key. Bucket: 1 đơn vị lưu trữ chứa 1 hoặc nhiều record 9 Chỉ mục nhiều cấp (Multilevel index) • Sử dụng trong trường hợp tập tin chỉ mục quá lớn • Cách thực hiện: Lưu chỉ mục sơ cấp trên ổ cứng và xây một chỉ mục thưa trên nó.
outer index Chỉ mục thưa inner index của chỉ mục sơ cấp Chỉ mục sơ cấp 10 6.1 Chỉ mục (indexing) (tt) Đặc Sơ cấp Được sắp Thưa Thứ cấp Chỉ mục B+ -cây Nhiều cấp 11 6.2 File chỉ mục B+ -Cây (B+-Tree Index file) • Nhược điểm của file chỉ mục tuần tự: giảm hiệu năng khi file lớn lên • Để khắc phục: đòi hỏi phải tổ chức lại file B+-cây là một cấu trúc tổ chức chỉ mục được sử dụng rộng rãi vì nó đảm bảo được tính hiệu quả bất chấp các hành động xen xoá.2 File chỉ mục B+ -Cây (tt) Nút bên phải sẽ có giá trị lớn hơn nút gốc Nút bên trái sẽ có tất cả các giá trị nhỏ hơn hoặc bằng nút gốc 13 6.2 File chỉ mục B+ -Cây (tt) v Cấu trúc của một nút lá B+ Tree có bậc p • Con trỏ dữ liệu chỉ xuất phát ở nút lá • Các Nút lá liên kết với nhau theo thứ tự khóa tìm kiếm 14 6.2 File chỉ mục B+ -Cây (tt) • Là một dạng cây cân bằng (mọi đường dẫn từ gốc đến lá có cùng độ dài) • Mỗi nút không là lá có số con (pointer) nằm trong khoảng [m/2].m, m là 1 số cố định gọi là bậc của cây • Mỗi nút lá có số giá trị (key) nằm trong khoảng [(m-1)/2]. m-1 • Nút gốc (nếu không phải nút lá) có ít nhất 2 nút con • Mọi nút lá đều nằm cùng một mức 15 File chỉ mục B+ -cây - THÊM • Ý tưởng: Tìm vị trí khóa có thể thêm vào cây. Khóa mới sẽ được thêm vào nút lá: – Nếu chưa đầy → Thêm khóa mới vào là hoàn tất – Nếu đầy → Tách nút lá ra làm hai nút cạnh nhau trong cùng một mức. Cụ thể: chuyển phần tử giữa lên nút cha • Quá trình tách nút có thể được lan truyền ngược về nút gốc và kết thúc khi có một nút cha nào đó cần được thêm 1 khóa từ dưới lên mà chưa đầy 16 Chèn (xen) khóa vào B+ -cây Ví dụ: • Cho B+ -cây bậc 3 rỗng • Hãy xây dựng B+ Tree bằng việc thêm lần lượt các khóa theo thứ tự sau: Công thức m=3 Nút Ít nhất Nhiều nhất Ít nhất Nhiều nhất Nút gốc 1 1 Nút trong m/2 m 3/2= 1.5 2 3 Nút lá (m-1)/2 m-1 (3-1)/2= 1 2 17 27 19 23 9 1 3 11 21 5 13 17 15 29 25 19 27 23 27 Tách nút Thêm nút: 9 và 1 23 1 9 19 23 27 Tách nút 18 27 19 23 9 1 3 11 21 5 13 17 15 29 25 9 23 3 9 19 23 27 Thêm nút: 3 và 11 9 23 1 3 9 11 19 23 27 Tách nút 19 27 19 23 9 1 3 11 21 5 13 17 15 29 25 Tách nút 9 11 23 1 3 9 11 19 23 27 11 9 23 1 3 9 11 19 23 2720 27 19 23 9 1 3 11 21 5 13 17 15 29 25 11 9 23 1 3 9 19 11 19 21 23 27 Tách nút 11 9 19 23 1 3 9 11 19 21 23 27 21 27 19 23 9 1 3 11 21 5 13 17 15 29 25 11 9 19 23 1 3 5 9 11 19 21 23 27 Tách nút 11 3 9 19 23 1 3 5 9 11 19 21 23 27 22 27 19 23 9 1 3 11 21 5 13 17 15 29 25 11 3 9 19 23 1 3 5 9 11 13 17 19 21 23 27 Tách nút 11 19 3 9 13 23 1 3 5 9 11 13 17 19 21 23 27 23 23 27 19 23 9 1 3 11 21 5 13 17 15 29 25 11 19 3 9 13 23 1 3 5 9 11 13 15 17 19 21 23 27 24 11 19 3 9 13 15 23 1 3 5 9 11 13 15 17 19 21 23 27 24 24 27 19 23 9 1 3 11 21 5 13 17 15 29 25 11 19 3 9 13 15 23 1 3 5 9 11 13 15 17 19 21 23 27 29 Tách nút 11 19 3 9 13 15 23 27 1 3 5 9 11 13 15 17 19 21 23 27 29 25 27 19 23 9 1 3 11 21 5 13 17 15 29 25 Kết quả cuối cùng: 11 19 3 9 13 15 23 27 1 3 5 9 11 13 15 17 19 21 23 27 29 26 N=3 Brighton Clearview Downtown Giả sử bây giờ ta chèn thêm record: Clearview, A-777, 1000 vào trong CSDL 27 Brig Clearview Down Clearview Clearview 28 Downtown Mianus Redwood Clearview Clearview Downto Downt 29 File chỉ mục B+ -cây - XÓA Thao tác thực hiện: 1.
Tìm nút lá chứa khóa cần xóa 2. Xóa khóa trong nút lá tìm được 1 trong các cách sau: 2.1 Trường hợp đơn giản, xóa khóa cây vẫn đúng cấu trúc 2.2 Trường hợp nút lá có ít hơn k khóa (trong đó, m = 2k+1), thực hiện tái cân bằng cây: (a) Nếu 1 nút kề có nhiều hơn k khóa, chuyển một khóa sang (b) Ngược lại, thực hiện gộp lại với một nút kề (cha sẽ giảm đi một nút con) 30 File chỉ mục B+ -cây - XÓA Thao tác thực hiện (tiếp theo): 2.3 Trường hợp nút trung gian có ít hơn k khóa, lặp lại thao tác tái cân bằng cây như ở bước 2. Nếu thực hiện gộp đến nút gốc và nút gốc chỉ còn 1 nút con, thì cho nút con làm nút gốc mới 31 2.1 Cây không thay đổi cấu trúc: Xóa khóa D m=5 H A E I J. m = 2k+1 5=2k+1 5 -1= 2k k=2 Số phần tử tối thiểu: (m-1)/2= 2 Số phần tử tối đa: m-1= 4 32 2.2 Nút lá có ít hơn k khóa thực hiện tái cân bằng cây (a) Nút kề có nhiều hơn k khóa, chuyển 1 khóa sang H m=5 A E I J k=2.
v Nút kề anh em trái H A D I J .2 Nút lá có ít hơn k khóa thực hiện tái cân bằng cây (a) Nút kề có nhiều hơn k khóa, chuyển 1 khóa sang H m=5 A D I J k=2. v Nút kề anh em phải H A E I J .2 Nút lá có ít hơn k khóa thực hiện tái cân bằng cây (b) Gộp lại với một nút kề (cha sẽ giảm đi một nút con) G m=5 k=2 A D H I J. v Gộp nút lá G A Nút trung gian ít hơn k khóa H I J .3 Trường hợp nút trung gian có ít hơn k khóa, lặp lại thao tác tái cân bằng cây như ở bước 2.2 v Thực hiện gộp ở nút cha m=5 k=2 H A G I J. Gộp đến nút gốc và nút gốc chỉ còn 1 nút con, thì cho nút con làm nút gốc mới G m=5 k=2 A D H I.
37 Trường hợp xóa nút gốc xóa G m=5 k=2 A D H I thay thế. v Quay lại bước 3: Gộp nút gốc A F H I. 38 Xoá khóa:Downtown ra khỏi B+-cây 39 6. Chỉ mục và băm Chỉ mục Băm Chỉ mục Băm tĩnh được sắp Chỉ mục Băm B+-cây động 40 6.2 Băm (hashing) • Hạn chế của cơ chế tổ chức file tuần tự là: – Phải truy cập cấu trúc chỉ mục để định vị dữ liệu – Hoặc phải sử dụng tìm kiếm nhị phân – Tốn nhiều thời gian cho các thao tác I/O • Kỹ thuật băm giúp bỏ qua các thao tác truy xuất cấu trúc Index.