那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

tokyocabinet1.4.19阅读笔记(五)hash数据库插入数据流程

有了前面的基础,本节讲解插入数据的流程.

插入数据的实现代码,在函数tchdbputimpl中,首先这个函数会查找要插入记录的key是否已经存在,如果存在了,有很多case需要处理,在这里就不一一关注了,仅关注缺省的行为:如果key已经存在,那么覆盖原来的记录.否则,就插入新的记录.

所以,这里仅关注最简单的两种情况:如果存在就覆盖,如果不存在则插入新的记录.

1) 覆盖原记录
这里又区分两种情况:
a) 原有记录的尺寸不够插入新的记录,比如原有的记录是10个字节,但是新的记录需要20字节.这时候,首先会去调用上一节提到的tchdbfbpsplice 函数去尝试着合并该记录邻近的空闲记录形成一个更大尺寸的记录块,上一节中没有仔细说明这个函数.tchdbfbpsplice 的伪码大致如下:
当还有空闲块可以合并
       继续合并空闲块
如果合并之后的尺寸仍然不能满足要求,返回false
如果合并之后的尺寸大于所要求尺寸的两倍
       将多余的部分写入合适的freepool中
返回true,表示找到合适的块
所以,假如合并成功有足够的尺寸,那么就直接将新的记录写入就好了.
否则,如果不能够满足又合并不到更大的块,则会将原先的记录块首先写入到freepool中(tchdbwritefb函数 ),接着直接在当前的freepool中查找合适的块(tchdbfbpsearch函数),如果找到合适的块,那么也写入新的记录即可.否则,上面的合并和查找空闲块的操作都失败了,则需要增加数据库文件的尺寸插入新的记录了.

b) 原有记录足够插入新的记录
这种情况下,还要判断旧的尺寸对于新的记录是不是过大了,过大的话也需要调整.

2) 新增新的记录
这种情况的处理很简单了,可以看作是上面的情况a)的一种情况,即接着直接在当前的freepool中查找合适的块(tchdbfbpsearch函数),如果找到合适的块,那么也写入新的记录即可.否则,则需要增加数据库文件的尺寸插入新的记录了.

注意,在上面的查找freepool过程中,如果失败的话,将增加一个计数,当这个计数大于一个值时,将对整个freepool做一个调整,调整算法前一节已经提及.

以上,就是插入新纪录的两种最简单情况的流程,如果对之前的freepool管理很清楚的话,理解起来不是难事,因为插入新的记录主要还是考虑如何回收利用原有的空闲块罢了.




posted on 2010-01-25 23:21 那谁 阅读(6855) 评论(4)  编辑 收藏 引用 所属分类: tokyo cabinet

评论

# re: tokyocabinet1.4.19阅读笔记(五)hash数据库插入数据流程  回复  更多评论   

·空闲块池默认1024个,超过1024怎么办?
·空闲块池中的按位置排序和按大小排序的实现和目的是什么?
我读源码的时候这部分还没搞懂,有什么心得可以交流下!
:-)
2010-01-27 12:58 | 阿福

# re: tokyocabinet1.4.19阅读笔记(五)hash数据库插入数据流程  回复  更多评论   

@阿福
当当前freepool超过一定数量时,会进行merge操作进行整理。

按位置排序是为了merge合并方便。
按尺寸排序是为了根据所要求的尺寸进行二分查找方便。
这两点前面一节都有提到。

2010-01-29 12:21 | 那谁

# re: tokyocabinet1.4.19阅读笔记(五)hash数据库插入数据流程  回复  更多评论   

感觉对freepool这块的设计并不是很好,首先它是定量的,这样很容易出现超过且又无法合并的情况。不过它这样设计确保查找 free 块的速度。

此外不知tc在设计时是否采用了“对齐”或 block 的作法,这样对于长短相差不多的存取有点优势,虽然浪费了点空间。


2010-02-01 23:36 | hightman

# re: tokyocabinet1.4.19阅读笔记(五)hash数据库插入数据流程  回复  更多评论   

tchdbputimpl函数里面
rec.rsiz = hdb->ba64 ? sizeof(uint8_t) * 2 + sizeof(uint64_t) * 2 + sizeof(uint16_t) :
sizeof(uint8_t) * 2 + sizeof(uint32_t) * 2 + sizeof(uint16_t);
if(ksiz < (1U << 7)){
rec.rsiz += 1;
} else if(ksiz < (1U << 14)){
rec.rsiz += 2;
} else if(ksiz < (1U << 21)){
rec.rsiz += 3;
} else if(ksiz < (1U << 28)){
rec.rsiz += 4;
} else {
rec.rsiz += 5;
}
if(vsiz < (1U << 7)){
rec.rsiz += 1;
} else if(vsiz < (1U << 14)){
rec.rsiz += 2;
} else if(vsiz < (1U << 21)){
rec.rsiz += 3;
} else if(vsiz < (1U << 28)){
rec.rsiz += 4;
} else {
rec.rsiz += 5;
}
if(!tchdbfbpsearch(hdb, &rec)){
HDBUNLOCKDB(hdb);
return false;
}
rec.hash = hash;
rec.left = 0;
rec.right = 0;
rec.ksiz = ksiz;
rec.vsiz = vsiz;
rec.psiz = 0;
rec.kbuf = kbuf;
rec.vbuf = vbuf;
if(!tchdbwriterec(hdb, &rec, bidx, entoff)){
HDBUNLOCKDB(hdb);
return false;
}
这段程序进行tchdbfbpsearch之前rec.rsiz应该不是记录的总长度吧,还应该要加上ksiz和vsiz吧,代码改为
rec.rsiz = hdb->ba64 ? sizeof(uint8_t) * 2 + sizeof(uint64_t) * 2 + sizeof(uint16_t) :
sizeof(uint8_t) * 2 + sizeof(uint32_t) * 2 + sizeof(uint16_t);
if(ksiz < (1U << 7)){
rec.rsiz += 1;
} else if(ksiz < (1U << 14)){
rec.rsiz += 2;
} else if(ksiz < (1U << 21)){
rec.rsiz += 3;
} else if(ksiz < (1U << 28)){
rec.rsiz += 4;
} else {
rec.rsiz += 5;
}
if(vsiz < (1U << 7)){
rec.rsiz += 1;
} else if(vsiz < (1U << 14)){
rec.rsiz += 2;
} else if(vsiz < (1U << 21)){
rec.rsiz += 3;
} else if(vsiz < (1U << 28)){
rec.rsiz += 4;
} else {
rec.rsiz += 5;
}

//此处添加代码
rec.rsiz += ksiz+vsiz

if(!tchdbfbpsearch(hdb, &rec)){
HDBUNLOCKDB(hdb);
return false;
}
rec.hash = hash;
rec.left = 0;
rec.right = 0;
rec.ksiz = ksiz;
rec.vsiz = vsiz;
rec.psiz = 0;
rec.kbuf = kbuf;
rec.vbuf = vbuf;
if(!tchdbwriterec(hdb, &rec, bidx, entoff)){
HDBUNLOCKDB(hdb);
return false;
}


还是我理解有误啊,求指教
2015-01-15 21:14 | hm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理