Bài giảng Cấu trúc dữ liệu và giải thuật: Chỉ mục (Index) - Nguyễn Tri Tuấn

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chỉ mục (Index) - Nguyễn Tri Tuấn

1. Data Structure & Algorithms Chỉ mục (Index) Nguyễn Tri Tuấn Khoa CNTT – ĐH.KHTN.Tp.HCM Email: nttuan@ fit.hcmuns.edu.vn Chỉ mục -Index Giới thiệu Định nghĩa Dense or sparse Index Multi-level Index B+ Tree Index Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM2 1
2. Giới thiệu ªVídụthực tế: Hãy nêu ra vài vídụ trong đời sống thực tế màbạn biết về chỉ mục ? ªLợi ích của chỉ mục làgì? Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM3 Giới thiệu (tt) ªBảng dữ liệu (data table) trên máy tính: Tương tự như thư viện; mỗi record là1 cuốn sách Số mẫu tin (record) lớn Mẫu tin cónhiều field à kích thước mẫu tin lớn à kích thước bảng dữ liệu lớn Các mẫu tin không sắp theo thứ tự khoátìm kiếm Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM4 2
3. Giới thiệu (tt) ª3 khuyết điểm lớn với cách lưu trữ trên file tuần tự: Tốc độ tìm kiếm chậm Không an toàn Không cónhiều tiêu chítìm kiếm khác nhau Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM5 Giới thiệu (tt) Bảng dữ liệu với các record sort theo “Tên” Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM6 3
4. Định nghĩa ªIndex: làmột tập hợp các phần tử chỉ mục (Index entry) được tổ chức theo một qui tắc xác định nhằm tăng tốc độ tìm kiếm trên bảng dữ liệu ªPhần tử chỉ mục: làcấu trúc gồm tối thiểu 2 thuộc tính: Search key: một (hay nhiều) thuộc tính, được dùng để tìm kiếm các record trong bảng dữ liệu Pointer: con trỏ tham chiếu đến mẫu tin tương ứng với “Search key” Search key Pointer Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM7 Định nghĩa (tt) Chỉ mục với pointer tham chiếu đến bảng dữ liệu Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM8 4
5. Định nghĩa (tt) ªCác tính chất của chỉ mục: Kích thước nhỏ hơn nhiều so với bảng dữ liệu Tốc độ tìm kiếm nhanh Cóthể tạo nhiều chỉ mục khác nhau cho cùng 1 bảng dữ liệu à tìm kiếm trên các search key khác nhau Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM9 Dense Index Mỗi search-key sẽ cómột Index-entry tương ứng Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM10 5
6. Sparse Index ªChỉ tạo Index-entry cho một số search-key ªÁp dụng khi search-key được sắp thứ tự ªÍt tốn chi phíkhi Insert/Delete record trong bảng dữ liệu ªVề cơ bản, tốc độ tìm kiếm sẽ chậm hơn Dense Index Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM11 Sparse Index (tt) Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM12 6
7. Sparse Index (tt) ªCâu hỏi: Làm sao ứng dụng Sparse Index trong thực tế ? Tốc độ truy xuất / điều kiện khoá được sắp thứ tự ? à Multi-level Index Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM13 Multi-level Index ªĐể giảm thiểu số lần truy cập đĩa: Ta tạo ra một chỉ mục chính (primary index) cho bảng dữ liệu Vàtạo một Sparse Index trên primary index đó ªPrimary index lưu trên đĩa ªSparse Index lưu trong bộ nhớ chính: AVL, Red/Black tree, Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM14 7
8. Chỉ mục 2 cấp Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM15 Multi-level Index (tt) ªNếu số phần tử của Sparse index không đủ nhỏ để lưu trong bộ nhớ chính, ta sẽ tạo thêm Sparse index cho nó, ªIndex tại mỗi cấp đều phải được cập nhật khi thực hiện thao tác Insert/Delete record trong bảng dữ liệu Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM16 8
9. B+ tree Index ªKhảo sát cấu trúc Index của file chỉ mục *.IDX trong cơ sở dữ liệu FoxPro Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM17 Cấu trúc Header file *.IDX Byte offset Description 00–03 Pointer to the root node 04–07 Pointer to the free node list ( -1 if not present) 08–11 Pointer to the end of file (file size) 12–13 Length of key 14 Index options (any of the following numeric values or their sums): 1 –a unique index 8 –index has FOR clause 15 Index signature (for future use) 16–235 Key expression (uncompiled; up to 220 characters)1,3 236–455 FOR expression (uncompiled; up to 220 characters ending with a null value byte) 456–511 Unused Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM18 9
10. Cấu trúc 1 node trong file *.IDX Byte offset Description 00–01 Node attributes (any of the following numeric values or their sums): 0 –index node 1 –root node 2 –leaf node 02–03 Number of keys present (0, 1 or many) 04–07 Pointer to the node directly to left of the current node (on same level; -1 if not present) 08–11 Pointer to the node directly to right of the current node (on same level; -1 if not present) 12–511 Up to 500 characters containing the key value for the length of the key with a four-byte hexadecimal number stored in normal left-to-right format: If the node is a leaf (attribute = 02 or 03) then the four bytescontain an actual table number in hexadecimal format; otherwise, the 4 bytes contain an intra-index pointer.2 The key/four-byte hexadecimal number combinations will occur the number of times indicated in bytes 02–03. Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM19 B+ tree / *.IDX file Cấu trúc các node trong B+ tree của file chỉ mục *.IDX Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM20 10
11. B+ tree / *.IDX file Cấu trúc của 500 bytes dữ liệu (index-entry) tại mỗi node Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM21 Thank you for your attention Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM22 11
12. QQ && AA Winter 2006Data Structure & Algorithms -Index -Nguyen Tri Tuan, DH.KHTN Tp.HCM23 12