0.2 Lưu trữ và cấu trúc tập tin  (Page 19/26)

end else begin

p là chỉ số sao cho L'.Pp là con trỏ cuối trong L'

xoá (L'.Pp, L'.Kp) khỏi L'

xen (L'.Pp, L'.Kp) như phần tử đầu tiên trong L (right_shift tất cả các phần tử của L)

thay thế V' trong parent(L) bởi L'.Kp

end

end<đối xứng với trường hợp then>

end

end procedure

Tổ chức file B+-cây

Trong tổ chức file B+-cây, các nút lá của cây lưu trữ các mẩu tin, thay cho các con trỏ tới file. Vì mẩu tin thường lớn hơn con trỏ, số tối đa các mẩu tin được lưu trữ trong một khối lá ít hơn số con trỏ trong một nút không lá. Các nút lá vẫn được yêu cầu được lấp đầy ít nhất là một nửa.

Xen và xoá trong tổ chức file B+-cây tương tự như trong chỉ mục B+-cây.

Khi B+-cây được sử dụng để tổ chức file, việc sử dụng không gian là đặc biệt quan trọng, vì không gian bị chiếm bởi mẩu tin là lớn hơn nhiều so với không gian bị chiếm bởi (khoá,con trỏ). Ta có thể cải tiến sự sử sụng không gian trong B+-cây bằng cách bao hàm nhiều nút anh em hơn khi tái phân phối trong khi tách và trộn. Khi xen, nếu một nút là đầy, ta thử phân phối lại một số đầu vào đến một trong các nút kề để tạo không gian cho đầu vào mới. Nếu việc thử này thất bại, ta mới thực hiện tách nút và phân chia các đầu vào giữa một trong các nút kề và hai nút nhận được do tách nút. Khi xoá, nếu nút chứa ít hơn 2m/3 đầu vào, ta thử mượn một đầu vào từ một trong hai nút anh em kề. Nếu cả hai đều có đúng 2m/3 mẩu tin, ta phân phối lại các đầu vào của nút cho hai nút anh em kề và xoá nút thứ 3. Nếu k nút được sử dụng trong tái phân phối (k-1 nút anh em), mỗi nút đảm bảo chứa ít nhất (k-1)m/k đầu vào. Tuy nhiên, cái giá phải trả cho cập nhật của cách tiếp cận này sẽ cao hơn.

File chỉ mục b-cây (b-tree index files)

Chỉ mục B-cây tương tự như chỉ mục B+-cây. Sự khác biệt là ở chỗ B-cây loại bỏ lưu trữ dư thừa các giá trị khoá tìm kiếm. Trong B-cây, các giá trị khoá chỉ xuất hiện một lần. Do các khoá tìm kiếm xuất hiện trong các nút không là lá không xuất hiện ở bất kỳ nơi nào khác nữa trong B-cây, ta phải thêm một trường con trỏ cho mỗi khoá tìm kiếm trong các nút không là lá. Con trỏ thêm vào này trỏ tới hoặc mẩu tin trong file hoặc bucket tương ứng.

Một nút lá B-cây tổng quát có dạng:

Một nút không là lá có dạng:

Các con trỏ Pi là các con trỏ cây và được dùng như trong B+-cây. Các con trỏ Bi trong các nút không là lá là các con trỏ mẩu tin hoặc con trỏ bucket. Rõ ràng là số giá trị khoá trong nút không lá nhỏ hơn số giá trị trong nút lá. Số nút được truy xuất trong quá trình tìm kiếm trong một B-cây phụ thuộc nơi khoá tìm kiếm được định vị.

Xoá trong một B-cây phức tạp hơn trong một B+-cây. Xoá một đầu vào xuất hiện ở một nút không là lá kéo theo việc tuyển chọn một giá trị thích hợp trong cây con của nút chứa đầu vào bị xoá. Nếu khoá Ki bị xoá, khoá nhỏ nhất trong cây con được trỏ bởi Pi+1 phải được di chuyển vào vị trí của Ki. Nếu nút lá còn lại quá ít đầu vào, cần thiết các hoạt động bổ xung.

Định nghĩa chỉ mục trong sql

Một chỉ mục được tạo ra bởi lệnh CREATE INDEX với cú pháp