Lời mở đầu
Việc
tổ chức các cơ sở dữ liệu với một số lượng lớn các bản ghi là một công việc phức
tạp bởi nhiều ràng buộc, trong các ràng buộc đó quan trọng nhất là các ràng buộc
liên quan tới:
- Tốc độ tìm kiếm một bản ghi dựa vào key
- Tốc độ chèn/xóa một bản ghi
- Dung lượng bộ nhớ tiêu thụ để quản lý từng bản ghi và toàn bộ cơ sở dữ liệu
- Khả năng hoạt động của cơ sở dữ liệu trong môi trường multi-thread/multi-core
- Và nhiều ràng buộc khác liên quan tới thuộc tính kỹ thuật của chính phần mềm sử dụng cơ sở dữ liệu.
Các giao diện cơ bản
Trước hết khi thao tác với bảng, các giao diện cần thiết được thiết kế như sau:
Các giao diện cơ bản :
- Tạo bảng, cấp pháp bộ nhớ để lưu bảng, các phương thức của bảng và tất cả các bản ghi
- Xóa bảng, xóa tất cả các cấu trúc quản lý bản ghi và xóa bảng, giải phóng tất cả các loại bộ nhớ đã cấp pháp trong quá trình hoạt động của bảng để tránh memory leak
- Chèn một phần tử dựa vào key
- Xóa một phần tử dựa vào key
- Tính toán độ lớn của bảng
Các giao diện khác :
- Chuyển đổi các bản ghi lưu trong bảng thành lưu trong mảng hỗ trợ dump tất cả các bản ghi trong bảng
- Áp dụng một phương thức do người sử dụng định nghĩa cho tất cả các bản ghi trong bảng
Cấu trúc bảng và các phương thức cơ bản
Bảng bao gồm một mảng các phần tử mà mỗi phần tử lưu
giữ địa chỉ của một danh sách liên kết, các danh sách liên kết là nơi các bản
ghi trong bảng thực sự được tổ chức
Có hai phương thức cơ bản của bảng
là hash và compare
Việc tổ chức một bản ghi trong bảng
(chèn một phần tử dựa vào key) sẽ sử dụng hai phương thức cơ bản của bảng là
hash và compare, trong đó phương thức hash lấy đầu vào là key và đưa ra chỉ số
của mảng mà tại đó địa chỉ của danh sách liên kết được lưu giữ, khi đã biết
danh sách liên kết nào bản ghi được tổ chức, hàm compare được sử dụng để tìm kiếm
bản ghi đó (vẫn dựa vào key làm đầu vào), nếu bản ghi được tìm thấy(tức là bản
ghi đã tồn tại trong bảng) thì giá trị mới của bản ghi sẽ được update, ngược lại,
nếu bản ghi không được tìm thấy thì các cấu trúc dữ liệu quản lý bản ghi sẽ được
cấp pháp và bản ghi sẽ được chèn vào bảng
Tương
tự nếu xóa hay tìm kiếm một bản ghi từ bảng (xóa/tìm kiếm một phần tử dựa vào
key) cũng sẽ sử dụng hai phương thức trên để tìm kiếm danh sách liên kết chứa bản
ghi và tìm kiếm bản ghi trong danh sách liên kết, nếu bản ghi tồn tại trong bảng,
thì bản ghi sẽ được xóa bỏ khỏi bảng (xóa) hoặc trả về địa chỉ bản ghi (tìm kiếm).
Các cấu trúc dữ liệu cơ bản
Cấu trúc dữ liệu bảng như sau:
#define T Table_T
struct T {
int size;
int (*cmp)(const void *x, const void *y);
unsigned (*hash)(const void *key);
int length;
unsigned timestamp;
struct binding {
struct binding *link;
const void *key;
void *value;
} **buckets;
#define T Table_T
struct T {
int size;
int (*cmp)(const void *x, const void *y);
unsigned (*hash)(const void *key);
int length;
unsigned timestamp;
struct binding {
struct binding *link;
const void *key;
void *value;
} **buckets;
Cấu trúc dữ liệu Table(T) bao gồm
Trường size mô tả độ lớn tối đa của
bảng, độ lớn này được xác đinh ở thời điểm tạo bảng
Phương thức cmp (compare) và hash
hoạt động như mô tả bên trên
Trường length mô tả số lượng phần tử
của bảng, nó tăng lên khi một phần tử được chèn và giảm đi khi một phần tử bị
xóa khỏi bảng
Trường timestamp được cập nhật mỗi
khi có truy vấn vào bảng (chèn/xóa/sửa/…), sử dụng để chống lại hoạt động
multi-thread trong bảng vì hiện tại bảng không hỗ trợ tính năng này
Cấu trúc binding là nơi các bản ghi
được lưu lại trong một danh sách liên kết đơn, các bản ghi trỏ tới nhau bởi con
trỏ link, địa chỉ key của nó được lưu giữ trong trường key và địa chỉ bản ghi
được lưu trữ trong trường value, con trỏ ** của buckets mang hàm nghĩa con trỏ
trỏ tới mảng các con trỏ.
Các hàm cơ bản
Hàm tạo bảng
static int cmpatom(const
void *x, const void *y) {
return x != y;
}
static unsigned
hashatom(const void *key) {
return (unsigned long)key>>2;
}
T Table_new(int hint,
int cmp(const void *x, const void *y),
unsigned hash(const void *key)) {
T table;
int i;
static int primes[] = { 509, 509, 1021, 2053, 4093,
8191, 16381, 32771, 65521, INT_MAX };
assert(hint >= 0);
for (i = 1; primes[i] < hint; i++)
;
table = ALLOC(sizeof (*table) +
primes[i-1]*sizeof (table->buckets[0]));
table->size = primes[i-1];
table->cmp = cmp ? cmp
: cmpatom;
table->hash = hash ? hash : hashatom;
table->buckets = (struct binding **)(table + 1);
for (i = 0; i < table->size; i++)
table->buckets[i] = NULL;
table->length = 0;
table->timestamp = 0;
return table;
}
Hàm tạo bảng đưa vào trường hint để
xác định trước kích thước của bảng, dựa vào giá trị của hint mà một cấu hình gần
nhất (prime), làm tròn lên sẽ được cấp phát, kích thước được làm tròn lên này sẽ
lưu giữ trong trường size
Nếu người sử dụng khai báo phương thức compare
và hash của họ, hai phương thức này sẽ được sử dụng, ngược lại hai phương thức
compare và hash mặc định là cmpatom và hashatom sẽ được sử dụng, việc này để
tránh làm crash cơ sở dữ liệu khi người dùng không khai báo phương thức compare
và hash của họ
Tất cả các con trỏ trong mảng địa
chỉ danh sách liên kết khởi tạo về NULL, các trường khác khởi tạo tới 0 tương ứng
Hàm chèn một bản ghi vào bảng dựa vào key
void *Table_put(T table,
const void *key, void *value) {
int i;
struct binding *p;
void *prev;
assert(table);
assert(key);
i = (*table->hash)(key)%table->size;
for (p = table->buckets[i]; p; p = p->link)
if ((*table->cmp)(key, p->key) == 0)
break;
if (p == NULL) {
NEW(p);
p->key = key;
p->link = table->buckets[i];
table->buckets[i] = p;
table->length++;
prev = NULL;
} else
prev = p->value;
p->value = value;
table->timestamp++;
return prev;
}
Hàm lấy vào địa chỉ của bản ghi được lưu ở trường
value và địa chỉ key của bản ghi được lưu ở trường key, hàm sẽ dựa vào phương
thức hash (được lưu lúc tạo bảng) để tính toán chỉ số mảng con trỏ lưu địa chỉ
các danh sách liên kết, khi tìm ra danh sách liên kết sẽ chứa bản ghi, phương
thức compare được sử dụng để tìm xem bản ghi đã tồn tại trong bảng chưa, nếu bản
ghi chưa tồn tại, một cấu trúc dữ liệu được cấp phát lưu lại địa chỉ key, địa
chỉ của bản ghi và trả về NULL, ngược lại bản ghi đã tồn tại, nó sẽ được cập nhật
giá trị mới và giá trị cũ sẽ được trả về
Hàm xóa một bản ghi khỏi bảng
void *Table_remove(T table,
const void *key) {
int i;
struct binding **pp;
assert(table);
assert(key);
table->timestamp++;
i = (*table->hash)(key)%table->size;
for (pp = &table->buckets[i]; *pp; pp =
&(*pp)->link)
if ((*table->cmp)(key, (*pp)->key) == 0) {
struct binding *p = *pp;
void *value = p->value;
*pp = p->link;
FREE(p);
table->length--;
return value;
}
return NULL;
}
Tương tự như hàm chèn một phần tử
vào bảng, vị trí của bản ghi được tính toán trước, nếu bản ghi đang tồn tại
trong bảng, nó sẽ bị xóa khỏi bảng và địa chỉ của nó được trả về, ngược lại nếu
bản ghi không tồn tại, NULL sẽ được trả về
Hàm tìm kiếm một bản ghi dựa vào key
void *Table_get(T table,
const void *key) {
int i;
struct binding *p;
assert(table);
assert(key);
i = (*table->hash)(key)%table->size;
for (p = table->buckets[i]; p; p = p->link)
if ((*table->cmp)(key, p->key) == 0)
break;
return p ? p->value : NULL;
}
Hoàn toàn tương tự như hàm xóa bản ghi, nếu bản ghi tồn
tại, địa chỉ của nó sẽ được trả về, ngược lại NULL sẽ được trả về
Hàm trả về số lượng bản ghi trong bảng
int Table_length(T table) {
assert(table);
return table->length;
}Hàm tập hợp địa chỉ các bản ghi vào mảng
void **Table_toArray(T
table, void *end) {
int i, j = 0;
void **array;
struct binding *p;
assert(table);
array = ALLOC((2*table->length + 1)*sizeof (*array));
for (i = 0; i < table->size; i++)
for (p = table->buckets[i]; p; p = p->link) {
array[j++] = (void *)p->key;
array[j++] = p->value;
}
array[j] = end;
return array;
}
Hàm được sử dụng cho các mục đích
thống kê và tìm lỗi logic, hàm trả về con trỏ tới mảng các địa chỉ bản ghi, mảng
được cấp phát trong hàm, người sử dụng hàm phải giải phóng mảng sau khi sử dụng
để tránh memory leak
Hàm xóa bảng
void Table_free(T *table) {
assert(table && *table);
if ((*table)->length > 0) {
int i;
struct binding *p, *q;
for (i = 0; i < (*table)->size; i++)
for (p = (*table)->buckets[i]; p; p = q) {
q = p->link;
FREE(p);
}
}
FREE(*table);
}
Hàm xóa và giải phóng bộ nhớ của tất
cả các cấu trúc dữ liệu sử dụng để quản lý các bản ghi, đồng thời xóa luôn bảng,
hàm không bao gồm giải phóng các bản ghi.Người dùng phải tự giải phóng bộ nhớ
lưu giữ các bản ghi để tránh memory leak
Hàm áp dụng một phương thức do người dùng định nghĩa vào tất cả các bản ghi của bảng
void Table_map(T table,
void apply(const void *key, void **value, void *cl),
void *cl) {
int i;
unsigned stamp;
struct binding *p;
assert(table);
assert(apply);
stamp = table->timestamp;
for (i = 0; i < table->size; i++)
for (p = table->buckets[i]; p; p = p->link) {
apply(p->key, &p->value, cl);
assert(table->timestamp == stamp);
}
}
Hàm này đòi hỏi duyệt qua tất cả
các bản ghi của bảng, phương thức do người dùng định nghĩa có thể rất đa dạng từ
phân loại các bản ghi, tập hợp thông tin thống kê từ một loại bản ghi nào đó,
giải phóng bộ nhớ hoặc thay đổi thông tin của một trường trong bản ghi, hàm sử
dụng trường timestamp của bảng để chống lại hoạt động multi-thread trên bảng
trong thời gian hoạt động của hàm. Trong thời gian hàm được gọi, các hàm tác động
vào bản ghi như chèn/xóa/sửa không được gọi cùng thời điểm ở một CPU khác, nếu
không hàm sẽ khiến chương trình crash
Đánh giá hiệu năng của phương pháp
Phương pháp tổ chức dữ liệu bằng bảng rõ ràng có một hiệu năng tốt hơn các phương thức tổ chức dữ liệu cơ bản như mảng hoặc danh sách liên kết, tất nhiên. Xem xét tổ chức một cơ sở dữ liệu với 10000 bản ghi, nếu tổ chức dữ liệu bằng mảng hoặc danh sách liên kết, dù dữ liệu có được sắp xếp, , để chèn/xóa/tìm kiếm một bản ghi, số lần phải gọi hàm so sánh ít nhât cũng phải là log2(10000) ~ 14 lần , trong khi đó nếu tổ chức bằng bảng với 65535 phần tử mảng, thì mỗi khi thao tác chỉ phải gọi hàm hash một lần và hàm so sánh tối đa 2 lầnNhược điểm của phương pháp này là cấu trúc dữ liệu phức tạp hơn, gây ra tiềm ẩn lỗi nhiều gây crash cơ sở dữ liệu và mỗi khi crash cũng khó tìm hơn. Một nhược điểm khác là sử dụng bộ nhớ kém hiệu quả hơn. Tuy nhiên đối với các máy tính ngày nay bộ nhớ là rất rẻ
Chúng ta sẽ trở lại vấn đề này trong bài sau khi chúng ta sử dụng phương pháp này để tổ chức một bảng macvlan với 10000 bản ghi
Toàn bộ mã nguồn của framework các bạn có thê download tại GitHub của Nhã Uyên Education
https://github.com/nhauyeneducation/linux_systemtraining
Tin học Nhã Uyên là một tổ chức thành lập với mục tiêu đào tạo kỹ sư lập trình hệ thống, kỹ sư lập trình nhúng và kỹ sư lập trình mạng trên nền tảng hệ điều hành Linux/Unix tại Việt Nam.
Mời các bạn vào Facebook của Tin học Nhã Uyên tại
https://www.facebook.com/tinhocnhauyen/ để theo dõi các bài viết kỹ thuật chất lượng tiếp theo của Tin học Nhã Uyên. Xin trân trọng cảm ơn các bạn
Comments
Post a Comment