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.

thelam92