Tổng quan về BTree database đơn giản

735

04-04-2018

Module btree thực hiện một key-value database đơn giản bằng cách sử dụng bộ nhớ ngoài (disk files, hoặc random-access stream) . Trong bài viết này, Bizfly Cloud sẽ cùng bạn đọc tìm hiểu về cấu trúc dữ liệu dạng cây B-tree.

Tổng quan B-Tree

Keys được lưu trữ được sắp xếp trong cơ sở dữ liệu, bên cạnh việc truy xuất bằng key value, database cũng hỗ trợ quét phạm vi được sắp xếp (truy xuất các values với keys trong một phạm vi nhất định). Về phía giao diện ứng dụng, BTree database hoạt động theo standard dict, một khác biệt đáng chú ý là cả keys và values phải là đối tượng byte (vì vậy, nếu bạn muốn lưu trữ các đối tượng khác, bạn cần để chúng thành dạng byte trước).

Module dựa trên thư viện BerkelyDB nổi tiếng, phiên bản 1.xx.

Ví dụ

Chức năng

btree.open(stream, *, flags=0, pagesize=0, cachesize=0, minkeypage=0)

Mở database từ random-access stream (như open file). Tất cả các tham số khác là tùy chọn và keyword-only, và cho phép tinh chỉnh các tham số nâng cao của hoạt động cơ sở dữ liệu (hầu hết người dùng sẽ không cần chúng):

- flags: Hiện không sử dụng.

- pagesize: Kích thước trang được sử dụng cho các nút trong BTree. Phạm vi là 512-65536. Nếu 0, mặc định cổng cụ thể sẽ được sử dụng, được tối ưu hóa cho việc sử dụng bộ nhớ của cổng và/ hoặc hiệu suất.

- cachesize: Kích thước bộ nhớ cache được đề xuất theo byte. Đối với một board có đủ bộ nhớ sử dụng các giá trị lớn hơn có thể cải thiện hiệu suất. Chính sách bộ nhớ cache như sau: toàn bộ cache không được cấp phát cùng một lúc; thay vào đó, việc truy cập một trang mới trong cơ sở dữ liệu sẽ cấp phát memory buffer cho nó, cho đến khi giá trị được xác định bằng cachesize. Sau đó, các bộ đệm này sẽ được quản lý bằng chính sách LRU (least recently used). Các bộ đệm khác vẫn có thể được phân bổ nếu cần (ví dụ: nếu cơ sở dữ liệu chứa các keys và/ hoặc values lớn). Bộ đệm cache được phân bổ không được reclaimed.

- minkeypage: Số lượng keys tối thiểu để lưu trữ trên mỗi trang. Giá trị mặc định bằng 0 tương đương với 2.

BTree thực hiện một dictionary protocol (tập hợp các phương pháp) và một số phương pháp bổ sung được mô tả ngay sau đây.

Phương pháp

btree.close()

Đóng cơ sở dữ liệu. Bắt buộc phải đóng database vào cuối quá trình xử lý vì một số unwritten data có thể vẫn còn trong bộ nhớ cache. Lưu ý rằng điều này không đóng underlying stream với database đã được mở, nó phải được đóng riêng (cũng bắt buộc phải đảm bảo rằng dữ liệu được flushed từ buffer đến underlying storage).

btree.flush()

Flush bất kỳ dữ liệu nào trong bộ nhớ cache đến underlying stream.

btree.getitem(key), btree.get(key, default=None), btree.setitem(key, val), btree.detitem(key), btree.contains(key)

Phương pháp dictionary tiêu chuẩn.

btree.iter()

Một đối tượng BTree có thể được lặp qua trực tiếp (tương tự như một dictionary) để truy cập vào tất cả các keys theo thứ tự.

btree.keys([start_key[, end_key[, flags]]]), btree.values([start_key[, end_key[, flags]]]), btree.items([start_key[, end_key[, flags]]])

Các phương thức này tương tự như các phương pháp dictionary chuẩn, nhưng cũng có thể lấy các tham số tùy chọn để lặp key sub-range, thay vì toàn bộ database. Lưu ý rằng đối với tất cả 3 phương pháp, đối số start_key và end_key đại diện cho các key values.

Ví dụ, phương thức values() sẽ lặp qua các giá trị tương ứng với dãy khóa được đưa ra. Không có giá trị nào cho start_key có nghĩa là "from the first key", không có end_key hoặc giá trị None tức là "until the end of database". Theo mặc định, phạm vi bao gồm start_key và không gồm end_key, bạn có thể bao gồm end_key trong lần lặp lại bằng cách chuyển flag của btree.INCL. Bạn có thể lặp theo hướng giảm dần bằng cách pass flag btree.DESC. Các flags values có thể được ORED với nhau.