章节目录
T*-tree 的介绍
T*-tree 节点与C语言实现
T*-tree 的插入、删除、查找与旋转
实现简单的 key-value 内存数据库
参考文献
T-tree 和 T *-tree 极为相似，他们的不同主要是 T×-tree 的节点结构比 T -tree 多了一个指向 successor 的指针位, 指向 successor 的指针的存在是的树的寻找和遍历的时间复杂度. 注：本文中关于 ttree 的 head file：ttree.h 和 ttree_defs.h 来源于 Dan Kruchinin <dkruchinin@acm.org>，Github：dkruchinin/libttree
T*-tree 的介绍
在计算机科学中，T-tree 是一种二叉树，它有一个左子树和一个右子树，由主存储器数据库使用，例如 Datablitz，EXtremeDB，MySQL Cluster，Oracle TimesTen 和 MobileLite。T 树是一种平衡的索引树数据结构，针对索引和实际数据都完全保存在内存中的情况进行了优化，就像 B 树是针对面向块的辅助存储设备（如硬盘）上的存储而优化的索引结构。T 树寻求获得内存树结构（如 AVL 树）的性能优势，同时避免它们常见的大存储空间开销。T 树不保留索引树节点本身内的索引数据字段的副本。相反，它们利用了这样的事实：实际数据总是与索引一起在主存储器中，因此它们只包含指向实际数据字段的指针。
虽然 T 树以前被广泛用于主存数据库，但最近的研究表明它们在现代硬件上的表现并不比 B 树好。主要原因是现代的内存和硬盘的速度差异越来越大了，内存访问速度比硬盘访问速度快，并且 CPU 的核心缓存容量也越来越大。
T*-tree 的节点结构与 C 语言实现
T 树节点通常由指向父节点，左右子节点，有序数据指针数组和一些额外控制数据的指针组成。具有两个子树的节点称为内部节点（internal nodes），没有子树的节点称为叶子节点（leaf nodes），而仅具有一个子树的节点称为半叶节点（half-leaf nodes）。如果值在节点的当前最小值和最大值之间，则该节点称为（bounding node）。对于每个内部节点, 它的左子树中会有一个叶子节点或半叶子节点中有一个 predecessor（称为最大下限 -GLB(Greatest Lower Bound)），还在右子树中包含其最大数据值的后继者（LUB-lower upper bound）的节点(包含 GLB 或 LUP 的节点或许距离参照内部节点的距离很远, 但也有可能恰好相邻。正因为 T -tree 的每个节点是有序的，并且不同节点之间保证左子树的数据都比节点数据的最小值小，右子树的数据都比节点数据的最大值大，因此 B -tree 最左边的节点中最左边的数据是整棵树最小的数据，最右边的节点中的最大值是整棵树最大的数据。叶子和半叶节点中的数据元素量在 1~ 最大元素量之间，内部节点将其占用保持在预定义的最小元素量和最大元素数之间。如图：
T-tree，T-treenode 的插入、删除、旋转和查找代码来自于:Github:dkruchinin/libttree
typedef struct ttree_node {
struct ttree_node *parent; /**< Pointer to node’s parent */
struct ttree_node *successor; /**< Pointer to node’s soccussor */
union {
struct ttree_node *sides[2];
struct {
struct ttree_node *left; /**< Pointer to node’s left child */
struct ttree_node *right; /**< Pointer to node’s right child */
};
};
union {
uint32_t pad;
struct {
signed min_idx :12; /**< Index of minimum item in node’s array */
signed max_idx :12; /**< Index of maximum item in node’s array */
signed bfc :4; /**< Node’s balance factor */
unsigned node_side :4; /**< Node’s side(TNODE_LEFT, TNODE_RIGHT or TNODE_ROOT) */
};
};
T*-tree 的插入、删除、查找与旋转
插入
int ttree_insert(Ttree *ttree, void *item)
{
TtreeCursor cursor;
/*
* If the tree already contains the same key item has and
* tree’s wasn’t allowed to hold duplicate keys, signal an error.
*/
if (ttree_lookup(ttree, ttree_item2key(ttree, item), &cursor) && ttree->keys_are_unique) {
return -1;
}
ttree_insert_at_cursor(&cursor, item);
return 0;
}
void ttree_insert_at_cursor(TtreeCursor *cursor, void *item)
{
Ttree *ttree = cursor->ttree;
TtreeNode *at_node, *n;
TtreeCursor tmp_cursor;
void *key;
TTREE_ASSERT(cursor->ttree != NULL);
//TTREE_ASSERT(cursor->state == CURSOR_PENDING);
key = ttree_item2key(ttree, item);
n = at_node = cursor->tnode;
if (!ttree->root) {/* The root node has to be created. */
at_node = allocate_ttree_node(ttree);
at_node->keys[first_tnode_idx(ttree)] = key;
at_node->min_idx = at_node->max_idx = first_tnode_idx(ttree);
ttree->root = at_node;
tnode_set_side(at_node, TNODE_ROOT);
ttree_cursor_open_on_node(cursor, ttree, at_node, TNODE_SEEK_START);
return;
}
if (cursor->side == TNODE_BOUND) {
if (tnode_is_full(ttree, n)) {
/*
* If node is full its max item should be removed and
* new key should be inserted into it. Removed key becomes
* new insert value that should be put in successor node.
*/
void *tmp = n->keys[n->max_idx–];
increase_tnode_window(ttree, n, &cursor->idx);
n->keys[cursor->idx] = key;
key = tmp;
ttree_cursor_copy(&tmp_cursor, cursor);
cursor = &tmp_cursor;
/*
* If current node hasn’t successor and right child
* New node have to be created. It’ll become the right child
* of the current node.
*/
if (!n->successor || !n->right) {
cursor->side = TNODE_RIGHT;
cursor->idx = first_tnode_idx(ttree);
goto create_new_node;
}
at_node = n->successor;
/*
* If successor hasn’t any free rooms, new value is inserted
* into newly created node that becomes left child of the current
* node’s successor.
*/
if (tnode_is_full(ttree, at_node)) {
cursor->side = TNODE_LEFT;
cursor->idx = first_tnode_idx(ttree);
goto create_new_node;
}
/*
* If we’re here, then successor has free rooms and key
* will be inserted to one of them.
*/
cursor->idx = at_node->min_idx;
cursor->tnode = at_node;
}
increase_tnode_window(ttree, at_node, &cursor->idx);
at_node->keys[cursor->idx] = key;
cursor->state = CURSOR_OPENED;
return;
}
create_new_node:
n = allocate_ttree_node(ttree);
n->keys[cursor->idx] = key;
n->min_idx = n->max_idx = cursor->idx;
n->parent = at_node;
at_node->sides[cursor->side] = n;
tnode_set_side(n, cursor->side);
cursor->tnode = n;
cursor->state = CURSOR_OPENED;
fixup_after_insertion(ttree, n, cursor);
}
删除
void *ttree_delete(Ttree *ttree, void *key)
{
TtreeCursor cursor;
void *ret;
ret = ttree_lookup(ttree, key, &cursor);
if (!ret) {
return ret;
}
ttree_delete_at_cursor(&cursor);
return ret;
}
void *ttree_delete_at_cursor(TtreeCursor *cursor)
{
Ttree *ttree = cursor->ttree;
TtreeNode *tnode, *n;
void *ret;
TTREE_ASSERT(cursor->ttree != NULL);
TTREE_ASSERT(cursor->state == CURSOR_OPENED);
tnode = cursor->tnode;
ret = ttree_key2item(ttree, tnode->keys[cursor->idx]);
decrease_tnode_window(ttree, tnode, &cursor->idx);
cursor->state = CURSOR_CLOSED;
if (UNLIKELY(cursor->idx > tnode->max_idx)) {
cursor->idx = tnode->max_idx;
}
/*
* If after a key was removed, T*-tree node contains more than
* minimum allowed number of items, the proccess is completed.
*/
if (tnode_num_keys(tnode) > min_tnode_entries(ttree)) {
return ret;
}
if (is_internal_node(tnode)) {
int idx;
/*
* If it is an internal node, we have to recover number
* of items from it by moving one item from its successor.
*/
n = tnode->successor;
idx = tnode->max_idx + 1;
increase_tnode_window(ttree, tnode, &idx);
tnode->keys[idx] = n->keys[n->min_idx++];
if (UNLIKELY(cursor->idx > tnode->max_idx)) {
cursor->idx = tnode->max_idx;
}
if (!tnode_is_empty(n) && is_leaf_node(n)) {
return ret;
}
/*
* If we’re here, then successor is either a half-leaf
* or an empty leaf.
*/
tnode = n;
}
if (!is_leaf_node(tnode)) {
int items, diff;
n = tnode->left ? tnode->left : tnode->right;
items = tnode_num_keys(n);
/*
* If half-leaf can not be merged with a leaf,
* the proccess is completed.
*/
if (items > (ttree->keys_per_tnode – tnode_num_keys(tnode))) {
return ret;
}
if (tnode_get_side(n) == TNODE_RIGHT) {
/*
* Merge current node with its right leaf. Items from the leaf
* are placed after the maximum item in a node.
*/
diff = (ttree->keys_per_tnode – tnode->max_idx – items) – 1;
if (diff < 0) {
memcpy(tnode->keys + tnode->min_idx + diff,
tnode->keys + tnode->min_idx, sizeof(void *) *
tnode_num_keys(tnode));
tnode->min_idx += diff;
tnode->max_idx += diff;
if (cursor->tnode == tnode) {
cursor->idx += diff;
}
}
memcpy(tnode->keys + tnode->max_idx + 1, n->keys + n->min_idx,
sizeof(void *) * items);
tnode->max_idx += items;
}
else {
/*
* Merge current node with its left leaf. Items the leaf
* are placed before the minimum item in a node.
*/
diff = tnode->min_idx – items;
if (diff < 0) {
register int i;
for (i = tnode->max_idx; i >= tnode->min_idx; i–) {
tnode->keys[i – diff] = tnode->keys[i];
}
tnode->min_idx -= diff;
tnode->max_idx -= diff;
if (cursor->tnode == tnode) {
cursor->idx -= diff;
}
}
memcpy(tnode->keys + tnode->min_idx – items, n->keys + n->min_idx,
sizeof(void *) * items);
tnode->min_idx -= items;
}
n->min_idx = 1;
n->max_idx = 0;
tnode = n;
}
if (!tnode_is_empty(tnode)) {
return ret;
}
/* if we’re here, then current node will be removed from the tree. */
n = tnode->parent;
if (!n) {
ttree->root = NULL;
free(tnode);
return ret;
}
n->sides[tnode_get_side(tnode)] = NULL;
fixup_after_deletion(ttree, tnode, NULL);
free(tnode);
return ret;
}
查找
void *ttree_lookup(Ttree *ttree, void *key, TtreeCursor *cursor)
{
TtreeNode *n, *marked_tn, *target;
int side = TNODE_BOUND, cmp_res, idx;
void *item = NULL;
enum ttree_cursor_state st = CURSOR_PENDING;
/*
* Classical T-tree search algorithm is O(log(2N/M) + log(M – 2))
* Where N is total number of items in the tree and M is a number of
* items per node. In worst case each node on the path requires 2
* comparison(with its min and max items) plus binary search in the last
* node(bound node) excluding its first and last items.
*
* Here is used another approach that was suggested in
* “Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for
* Main Memory Database Management Systems”.
* It reduces O(log(2N/M) + log(M – 2)) to true O(log(N)).
* This algorithm compares the search
* key only with minimum item in each node. If search key is greater,
* current node is marked for future consideration.
*/
target = n = ttree->root;
marked_tn = NULL;
idx = first_tnode_idx(ttree);
if (!n) {
goto out;
}
while (n) {
target = n;
cmp_res = ttree->cmp_func(key, tnode_key_min(n));
if (cmp_res < 0)
side = TNODE_LEFT;
else if (cmp_res > 0) {
marked_tn = n; /* mark current node for future consideration. */
side = TNODE_RIGHT;
}
else {/* ok, key is found, search is completed. */
side = TNODE_BOUND;
idx = n->min_idx;
item = ttree_key2item(ttree, tnode_key_min(n));
st = CURSOR_OPENED;
goto out;
}
n = n->sides[side];
}
if (marked_tn) {
int c = ttree->cmp_func(key, tnode_key_max(marked_tn));
if (c <= 0) {
side = TNODE_BOUND;
target = marked_tn;
if (!c) {
item = ttree_key2item(ttree, tnode_key_max(target));
idx = target->max_idx;
st = CURSOR_OPENED;
}
else {/* make internal binary search */
struct tnode_lookup tnl;
tnl.key = key;
tnl.low_bound = target->min_idx + 1;
tnl.high_bound = target->max_idx – 1;
item = lookup_inside_tnode(ttree, target, &tnl, &idx);
st = (item != NULL) ? CURSOR_OPENED : CURSOR_PENDING;
}
goto out;
}
}
/*
* If we’re here, item wasn’t found. So the only thing
* needs to be done is to determine the position where search key
* may be placed to. If target node is not empty, key may be placed
* to its min or max positions.
*/
if (!tnode_is_full(ttree, target)) {
side = TNODE_BOUND;
idx = ((marked_tn != target) || (cmp_res < 0)) ?
target->min_idx : (target->max_idx + 1);
st = CURSOR_PENDING;
}
out:
if (cursor) {
ttree_cursor_open_on_node(cursor, ttree, target, TNODE_SEEK_START);
cursor->side = side;
cursor->idx = idx;
cursor->state = st;
}
return item;
}
旋转
static void __rotate_single(TtreeNode **target, int side)
{
TtreeNode *p, *s;
int opside = opposite_side(side);
p = *target;
TTREE_ASSERT(p != NULL);
s = p->sides[side];
TTREE_ASSERT(s != NULL);
tnode_set_side(s, tnode_get_side(p));
p->sides[side] = s->sides[opside];
s->sides[opside] = p;
tnode_set_side(p, opside);
s->parent = p->parent;
p->parent = s;
if (p->sides[side]) {
p->sides[side]->parent = p;
tnode_set_side(p->sides[side], side);
}
if (s->parent) {
if (s->parent->sides[side] == p)
s->parent->sides[side] = s;
else
s->parent->sides[opside] = s;
}
*target = s;
}
/*
* There are two cases of single rotation possible:
* 1) Right rotation (side = TNODE_LEFT)
* [P] [L]
* / \ / \
* [L] x1 => x2 [P]
* / \ / \
* x2 x3 x3 x1
*
* 2) Left rotation (side = TNODE_RIHGT)
* [P] [R]
* / \ / \
* x1 [R] => [P] x2
* / \ / \
* x3 x2 x1 x3
*/
static void rotate_single(TtreeNode **target, int side)
{
TtreeNode *n;
__rotate_single(target, side);
n = (*target)->sides[opposite_side(side)];
/*
* Recalculate balance factors of nodes after rotation.
* Let X was a root node of rotated subtree and Y was its
* child. After single rotation Y is new root of subtree and X is its child.
* Y node may become either balanced or overweighted to the
* same side it was but 1 level less.
* X node scales at 1 level down and possibly it has new child, so
* its balance should be recalculated too. If it still internal node and
* its new parent was not overwaighted to the opposite to X side,
* X is overweighted to the opposite to its new parent side,
* otherwise it’s balanced. If X is either half-leaf or leaf,
* balance racalculation is obvious.
*/
if (is_internal_node(n)) {
n->bfc = (n->parent->bfc != side2bfc(side)) ? side2bfc(side) : 0;
}
else {
n->bfc = !!(n->right) – !!(n->left);
}
(*target)->bfc += side2bfc(opposite_side(side));
TTREE_ASSERT((abs(n->bfc < 2) && (abs((*target)->bfc) < 2)));
}
/*
* There are two possible cases of double rotation:
* 1) Left-right rotation: (side == TNODE_LEFT)
* [P] [r]
* / \ / \
* [L] x1 [L] [P]
* / \ => / \ / \
* x2 [r] x2 x4 x3 x1
* / \
* x4 x3
*
* 2) Right-left rotation: (side == TNODE_RIGHT)
* [P] [l]
* / \ / \
* x1 [R] [P] [R]
* / \ => / \ / \
* [l] x2 x1 x3 x4 x2
* / \
* x3 x4
*/
static void rotate_double(TtreeNode **target, int side)
{
int opside = opposite_side(side);
TtreeNode *n = (*target)->sides[side];
__rotate_single(&n, opside);
/*
* Balance recalculation is very similar to recalculation after
* simple single rotation.
*/
if (is_internal_node(n->sides[side])) {
n->sides[side]->bfc = (n->bfc == side2bfc(opside)) ? side2bfc(side) : 0;
}
else {
n->sides[side]->bfc =
!!(n->sides[side]->right) – !!(n->sides[side]->left);
}
TTREE_ASSERT(abs(n->sides[side]->bfc) < 2);
n = n->parent;
__rotate_single(target, side);
if (is_internal_node(n)) {
n->bfc = ((*target)->bfc == side2bfc(side)) ? side2bfc(opside) : 0;
}
else {
n->bfc = !!(n->right) – !!(n->left);
}
/*
* new root node of subtree is always ideally balanced
* after double rotation.
*/
TTREE_ASSERT(abs(n->bfc) < 2);
(*target)->bfc = 0;
}
static void rebalance(Ttree *ttree, TtreeNode **node, TtreeCursor *cursor)
{
int lh = left_heavy(*node);
int sum = abs((*node)->bfc + (*node)->sides[opposite_side(lh)]->bfc);
if (sum >= 2) {
rotate_single(node, opposite_side(lh));
goto out;
}
rotate_double(node, opposite_side(lh));
/*
* T-tree rotation rules difference from AVL rules in only one aspect.
* After double rotation is done and a leaf became a new root node of
* subtree and both its left and right childs are half-leafs.
* If the new root node contains only one item, N – 1 items should
* be moved into it from one of its childs.
* (N is a number of items in selected child node).
*/
if ((tnode_num_keys(*node) == 1) &&
is_half_leaf((*node)->left) && is_half_leaf((*node)->right)) {
TtreeNode *n;
int offs, nkeys;
/*
* If right child contains more items than left, they will be moved
* from the right child. Otherwise from the left one.
*/
if (tnode_num_keys((*node)->right) >= tnode_num_keys((*node)->left)) {
/*
* Right child was selected. So first N – 1 items will be copied
* and inserted after parent’s first item.
*/
n = (*node)->right;
nkeys = tnode_num_keys(n);
(*node)->keys[0] = (*node)->keys[(*node)->min_idx];
offs = 1;
(*node)->min_idx = 0;
(*node)->max_idx = nkeys – 1;
if (!cursor) {
goto no_cursor;
}
else if (cursor->tnode == n) {
if (cursor->idx < n->max_idx) {
cursor->tnode = *node;
cursor->idx = (*node)->min_idx +
(cursor->idx – n->min_idx + 1);
}
else {
cursor->idx = first_tnode_idx(ttree);
}
}
}
else {
/*
* Left child was selected. So its N – 1 items
* (starting after the min one)
* will be copied and inserted before parent’s single item.
*/
n = (*node)->left;
nkeys = tnode_num_keys(n);
(*node)->keys[ttree->keys_per_tnode – 1] =
(*node)->keys[(*node)->min_idx];
(*node)->min_idx = offs = ttree->keys_per_tnode – nkeys;
(*node)->max_idx = ttree->keys_per_tnode – 1;
if (!cursor) {
goto no_cursor;
}
else if (cursor->tnode == n) {
if (cursor->idx > n->min_idx) {
cursor->tnode = *node;
cursor->idx = (*node)->min_idx + (cursor->idx – n->min_idx);
}
else {
cursor->idx = first_tnode_idx(ttree);
}
}
n->max_idx = n->min_idx++;
}
no_cursor:
memcpy((*node)->keys + offs,
n->keys + n->min_idx, sizeof(void *) * (nkeys – 1));
n->keys[first_tnode_idx(ttree)] = n->keys[n->max_idx];
n->min_idx = n->max_idx = first_tnode_idx(ttree);
}
out:
if (ttree->root->parent) {
ttree->root = *node;
}
}
实现简单的 key-value 内存数据库
实现简单的 key-value 内存数据库, 用 hashtable 来链接 key-value 的关系。key 不光插入到 ttree 中，而且还存到 hash-table 中。hash_table 采用了 macro：hash-table（uthash.h）`uthash.h 的帮助文档:macro：uthash.h 帮助文档 hashkey-value 对的插入: 插入之前先 HASH_FIND_INT 看看，key-value 存不存在，如果不存在则可以插，存在的话不能插入。
void add_user(int user_id, char *name) {
struct my_struct *s;
HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */
if (s==NULL) {
s = (struct my_struct *)malloc(sizeof *s);
s->id = user_id;
HASH_ADD_INT(users, id, s); /* id: name of key field */
}
strcpy(s->name, name);
}
解析存有 key-value 格式的文件
找到一个 key-value 格式的实例:xlarge.delfopen()读取文件, 读完之后 fclose()关闭。因为待会儿要用 strtok 来拆开每一行，所以 malloc 个 file_line
FILE * fp;
fp = fopen(“/home/vory/programing/c/key_value_mmdb/xlarge.del”,”r”);
file_line = malloc(1000 * sizeof(char));
memset(file_line, 0, 1000 * sizeof(char));
……
fclose(fp);
fgets 获取每一行:
char * buf;
buf = malloc(sizeof(input));
memset(buf,0,sizeof(input));
while(fgets(input ,256,fp)){
strcpy(buf,input);
……
}
strtok 切割每一行为若干字符串。strtok 将目标字符串的符合 delim 中的元素全部替换为 ’0′,strtok 用了之后，原来的目标代码就被破坏了，因此，新 malloc 一个接受复制的字符串，将目标字符串 strcpy()之后，对复制的字符串进行 strtok()操作。用完之后 free()。
strcpy(buf,source_string);
token = strtok(buf,delim);
// printf(“%s\n”,token);
parameter[parametercount] = malloc(sizeof(input));
strcpy(parameter[parametercount],token);
parametercount++;
token = strtok(NULL,delim);
// printf(“%s\n”,token);
parameter[parametercount] = malloc(sizeof(input));
strcpy(parameter[parametercount],token);
实例的 xlarge.del 文件的内容大概是这样：每一行分成两部分，KEY 和 VALUE 被逗号隔开着。
41231234,”Teenage Caveman”
3061234,”Banger Sisters, The”
18861234,”Hope Floats”
29381234,”No Looking Back”
1288,”Erotic Confessions: Volume 8″
2954,”Normal Life”
43901234,”Utomlyonnye solntsem”
20801234,”Island of Dr. Moreau, The”
3019,”One Hell of a Guy”
6712341,”Adventures of Pluto Nash, The”
33031234,”Pronto”
34701234,”Ripper, The”
106612341,”Devotion”
39481234,”Starship Troopers”
32381234,”Polish Wedding”
30551234,”Oscar and Lucinda”
42391,”Tomcats”
1661123411,”Gojira ni-sen mireniamu”
10611234,”Devil in a Blue Dress”
61612341,”Bully”
102612341,”Defenders: Taking the First, The”
1650,”Go Fish”
43512341,”Black Rose of Harlem”
解析从文件读来的每一行：每一行最多解析为2个参数([KEY] [VALUE])。
void parse_file(char * string){
char * buf;
char * delim;
delim = NULL;
delim = “,”;
char * token;
token = NULL;
buf = malloc(1000*sizeof(char));
memset(buf,0, 1000*sizeof(char));
if (!parf0){
parf0 =malloc(500*sizeof(char));
}
memset(parf0,0, 500*sizeof(char));
if (!parf1){
parf1 =malloc(500*sizeof(char));
}
memset(parf1,0, 500*sizeof(char));
strcpy(buf, string);
token = strtok(buf, delim);
if(token != NULL) {
strcpy(parf0, token);
}
token = strtok(NULL, delim);
if (token != NULL){
strcpy(parf1, token);
}
free(buf);
}
strtol 将字符型的数据转换成 long int 型:long int strtol(const char nptr,char *endptr,int base);strtol 不仅可以识别十进制整数，还可以识别其它进制的整数，取决于 base 参数，base 为 10，则识别十进制整数。
all_items[bcount].key = strtol(parf0,NULL ,10);
bcount++;
hash_user_id = strtol(parf0,NULL ,10);
strcpy(hash_name,parf1);
解析从命令行输入的命令（[COMMANDS] [KEY] [VALUE])
从文件读取每一行是 [KEY] [VALUE]的格式，但是从命令行读取是 [COMMANDS] [KEY] [VALUE] 的格式。我将 copy_string,par1，par2，par3 定义在了别处。这样就可以解析从 stdin 输入的句子了，被空格隔开的句子最多分为发出 3 路给 par1，par2，par3。如果 stdin 输入的句子只包含了一个空格（也就是含有 [COMMANDS] [KEY] 的结构）则只能被分发为 2 路给 par1 和 par2.malloc()之后要 free(), 我在别处 free() 了。
void parseinput(char *string){
char * delim;
delim = ” “;
copy_string = malloc(100*sizeof(char));
memset(copy_string,0,100* sizeof(char));
char * token;
token = NULL;
par1 = malloc(50*sizeof(char));
par2 = malloc(50*sizeof(char));
par3 = malloc(50*sizeof(char));
memset(par1,0,50*sizeof(char));
memset(par2,0,50*sizeof(char));
memset(par3,0,50*sizeof(char));
strcpy(copy_string,string);
printf(“%s is copystring .\n “,copy_string);
printf(“%s is string . \n”,string);
token = strtok(copy_string,delim);
if (token != NULL){
printf(“%s is token1 \n”,token);
strcpy(par1,token);
}
token = strtok(NULL,delim);
if (token != NULL){
printf(“%s is token2 \n”,token);
strcpy(par2,token);
}
token = strtok(NULL,delim);
if (token != NULL){
printf(“%s is token3 \n”,token);
strcpy(par3,token);
}
free(copy_string);
}
初始化 T *-tree
#define ttree_init(ttree, num_keys, is_unique, cmpf, data_struct, key_field) _ttree_init(ttree, num_keys, is_unique, cmpf, offsetof(data_struct, key_field))
int __ttree_init(Ttree *ttree, int num_keys, bool is_unique, ttree_cmp_func_fn cmpf, size_t key_offs);
………..
ret = ttree_init(&ttree, 8, false, __cmpfunc, struct item, key);
if (ret < 0) {
fprintf(stderr, “Failed to initialize T*-tree. [ERR=%d]\n”, ret);
free(all_items);
exit(EXIT_FAILURE);
}
将读取的每一行插入 t *tree，并将 key-value 插入 hashtable
在一个循环中解析每一行，当真个文件的所有行都读完则跳出循环。
while (fgets(file_line, 1000, fp)) {
parse_file(file_line);
all_items[bcount].key = strtol(parf0, NULL, 10);
hash_name = malloc(500 * sizeof(char));
memset(hash_name, 0, 500 * sizeof(char));
hash_user_id = strtol(parf0, NULL, 10);
strcpy(hash_name, parf1);
s = find_user(hash_user_id);
if (s == NULL) {add_user(hash_user_id, hash_name); }
free(hash_name);
memset(file_line, 0, 1000 * sizeof(char));
}
for (i = 0; i < num_keys; i++) {
ret = ttree_insert(&ttree, &all_items[i]);
if (ret < 0) {
fprintf(stderr, “Failed to insert item %d with key %ld! [ERR=%d]\n”, i, all_items[i].key, ret);
free(all_items);
exit(EXIT_FAILURE);
}
}
打印出 t *tree 的所有 key
for (i = 0; i < num_keys; i++) {
printf(“%ld “, all_items[i].key);
}
给 t *tree 的所有 key 排序
从小到大排序，递归实现。
printf(“\nSorted keys:\n”);
printf(“{ “);
tnode = ttree_node_leftmost(ttree.root);
while (tnode) {
tnode_for_each_index(tnode, i) {
printf(“%d “, *(int *) tnode_key(tnode, i));
}
tnode = tnode->successor;
}
printf(“}\n”);
程序结束前 free()，释放内存空间
ttree_destroy(&ttree);
free(all_items);
附件 & 代码
github 代码
所有的代码
参考文献
[1].Tobin J. Lehman and Michael J. Carey. 1986. A Study of Index Structures for Main Memory Database Management Systems. In Proceedings of the 12th International Conference on Very Large Data Bases (VLDB ’86), Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 294-303.[2].Kong-Rim Choi and Kyung-Chang Kim, “T*-tree: a main memory database index structure for real time applications,” Proceedings of 3rd International Workshop on Real-Time Computing Systems and Applications, Seoul, South Korea, 1996, pp. 81-88.doi: 10.1109/RTCSA.1996.554964[3].wikipidia about T-tree[4].An Open-source T*-tree Library