DB4: index bị chậm - P1

Tham khảo: use-the-index-luke
xem lại ví dụ ở DB3 - tìm kiếm số 57.

1. database tìm số 57 trong node này những vẫn có khả năng lại có số 57 trong node khác nên nó vẫn phải tìm tiếp
2. Yếu tố thứ 2 làm index chậm là việc accessing the table
khi truy vấn data theo index gồm 3 bước: - Duyệt cây cân bằng (the tree traversal)
- Duyệt theo các leaf node (following the leaf node chain)
- Lấy dữ liệu trong bảng (fetching the table data)
-> theo lý thuyết thì bước duyệt cây cân bằng là nhanh rồi
vậy lý do index vẫn chậm chỉ có thể xảy ra ở bước 2 or 3 or cả 2.
chậm do ở bước 2 (Bước duyệt theo leaf node chậm):
trong thực tế giá trị cần tìm có thể nằm trên nhiều leaf node khác nhau nên database phải duyệt hết các leaf node này để đảm bảo rằng lấy đúng data
chậm do ở bước 3 (Bước lấy dữ liệu trong bảng chậm):
Trong trường hợp một leaf node có thể chứa nhiều cục index (thường là hàng trăm) nhưng khi lấy dữ liệu từ bảng thì mỗi cục dữ liệu trong bảng có thể nằm trên nhiều block khác nhau:
Oracle database mô tả ba hoạt động riêng biệt mô tả một tra cứu index cơ bản:
1. INDEX UNIQUE SCAN
The INDEX UNIQUE SCAN chỉ thực thi bước 1 ở trên (duyệt cây cân bằng)
The Oracle database dùng hoạt động này khi ràng buộc tìm kiếm chỉ trả về duy nhất 1 bản ghi
ex: select StudentID from Student where StudentID=1
2. INDEX RANGE SCAN
The INDEX RANGE SCAN thực thi duyệt cây cân bằng và thực thi tiếp the leaf node chain để tìm kiếm tất cả bản ghi thỏa mãn.
ex: select StudentID from Student where StudentID <= 10
3. TABLE ACCESS BY INDEX ROWID
ex: select StudentID, StudentName from Student where StudentID=1;
Do StudentName ko có trong index nên database sẽ phải dùng đến thao tác: TABLE ACCESS BY INDEX ROWID để tìm

DB3: The Search Tree (B-Tree) Makes the Index Fast

Tham khảo: use-the-index-luke
Lưu ý: A B-tree is a balanced tree—not a binary tree.
Do các index leaf node đc lưu trữ theo thứ tự tùy ý - có nghĩa là vị trí các index leaf node này ở trên disk không trùng với vị trí logic (logical position)theo thứ tự index.
Nên cần 1 cấu trúc dữ liệu nữa là B-Tree -> The balanced search tree, để tìm kiếm nhanh hơn
Hình sau mô tả cấu trúc B-Tree

nhìn hình trên ta thây:
Mỗi branch node entry tương ứng với giá trị lớn nhất trong mỗi leaf node;
The next layer cũng tương tự. Việc này sẽ lặp đi lặp lại cho đến khi all keys fit into a single node, the root node.
1 khi index đc tạo thì database sẽ maintains 1 cách tự động. điều này dẫn đến mỗi lệnh: insert, delete, update sẽ tiêu tốn nhiều time
B-Tree Traversal

Hình trên mô tả 1 index fragment để biểu diễn tìm kiếm key “57”.
cây này sẽ duyệt từ root node, theo thứ tự tằng dần, đến khi >= 57 thì nhảy sang node gần hơn.
cứ lặp đi lặp lại như vậy cho đến leaf node
The B-tree enables the database to find a leaf node quickly.

DB2: The Index Leaf Nodes

Tham khảo: use-the-index-luke
Mục đích chính của index là biểu diễn các data đã đánh index theo thứ tự.
1 câu lệnh insert cần di chuyển toàn bộ data phía sau đi chỗ khác để dành chỗ cho item cần insert vào
-> quá tốn nhiều time
-> very slow
-> Giải pháp cho vấn đề là thiết lập một trật tự logic (logical order) độc lập với trật tự vật lý trong bộ nhớ.
The logical order is established via a doubly linked list
doubly linked list:
. Every node has links to two neighboring entries
. New nodes are inserted between two existing nodes by updating their links to refer to the new node
. The physical location of the new node doesn’t matter because the doubly linked list maintains the logical order.
-> It enables the database to read the index forwards or backwards as needed
. It is thus possible to insert new entries without moving large amounts of data—it just needs to change some pointers.

- Databases use doubly linked lists to connect the so-called index leaf nodes
- Each leaf node is stored in a database block or page
- All index blocks are of the same size—typically a few kilobytes

Hình ảnh: Mô tả the index leaf nodes và sự kết nối của nó tới the table data,
Mỗi index entry bao gồm the indexed columns (the key, column 2) and refers to the corresponding table row (via ROWID or RID).
Không giống như index, the table data được lưu trữ trong a heap structure và hoàn toàn chưa đc sắp xếp.
There is neither a relationship between the rows stored in the same table block nor is there any connection between the blocks.

DB1: giới thiệu về index

Tham khảo: use-the-index-luke
- index là 1 cấu trúc riêng biệt trong database
- dùng câu lệnh: "create index" để tạo index
- index có 1 vùng riêng để lưu trữ trên ổ đĩa
- index sẽ nắm giữ một bản sao dữ liệu đã được đánh index của bảng
- database sẽ tự tạo index trên primary key dù bạn có dùng lệnh tạo hay không
- khi đánh index có nhiều trường, phải quan tâm đến thứ tự của các trường này (điều này rất quan trọng)
-> Điều đó có nghĩa là một index là 1 pure redundancy (thuần túy chỉ là dự phòng)

- Tạo index không thay đổi dữ liệu của bảng
- index chỉ tạo ra một cấu trúc dữ liệu mới và tham chiếu đến bảng

-> tóm lại, index trong database nghe có vẻ giống như mục lục của cuốn sách, cụ thể:
- nó cũng chiếm 1 phần lưu trữ (như mục lục cần vài trang sách)
- nó cũng có thể là dư thừa (như mục lục cũng có thể ko cần đến - ko có mục lục thì vẫn có thể tìm đc các trang sách)
- nó cũng refer đến các dữ liệu cụ thể (như mục lục refer tới các trang cụ thể)

[Speed Master Choukai][Practice] - Mondai 1

おごり：treat

Daily Listening N3 - unit 11

Daily Listening N3 - unit 10

Daily Listening N3 - unit 9

Daily Listening N3 - unit 8

Daily Listening N3 - unit 7

Daily Listening N3 - unit 6

Daily Listening N3 - unit 5