HASH
数据库
TC
通过
hash
算法获取记录
,
如果桶数组有足够多的元素
,
时间复杂度就是
O(1),
也就是说
,
抓取一条记录需要的时间是一个常量
,
而与数据库的规模无关
,
这对于存储和删除是等效的
.hash
值的冲突通过二叉搜索树解决
,
也就是说即便桶只有极少的元素
,
也可以保证搜索的时间复杂度在
O(logn)
附近
TC
在通过加载整个桶数组到内存来改善检索
.
如果桶数组在内存中
,
它可能对于目标区域的访问只需要一次文件操作的路径访问
,
一个保存在文件中的桶数组并不是调用
’read’
而是通过
mmap(
内存文件映射
)
来调用的
,
因此
,
数据库连接的准备时间很短
,
并且两个或多个进程可以共享相同的内存映射
.
如果桶数组的元素个数大概是数据库总记录数的一半
, although it depends on characteristic of the input,
hash
值的冲突概率约为
56.7%(
桶数组大小和数据库记录数相同时为
36.8%,
桶数组大小为数据库记录数两倍时为
21.3%, 4
倍时为
11.5%, 8
倍时为
6.0%),
在这种情况下
,
对于一次检索而言
,
最多会有两次文件操作
.
如果把这个看作一个性能指标
,
为了处理百万记录的数据库
,
桶数组需要大概
50
万元素
,
每个元素的大小是
4byte(
应该存储的是地址
),
也就是说只要有
2M
的可用内存
,
就可以处理
100
万条记录的数据存取
.
传统的
DBM
提供两种模式的存储操作
: ‘insert’
和
’replace’,
在将要插入的
key
已经存在于数据库中时
, ‘insert’
模式会保留原值不变
, ‘replace’
模式则将该
key
对应的值替换为指定的新值
.
除了这两种模式
, TC
提供了
’concatenate’
模式
,
这种模式下
,
指定的值会连接到已经存在的值的末尾并存储
,
这个特性在处理向数组中增加元素时非常有用
.
TC
对碎片的处理有两种方式
,
一种是调用静态的优化
,
把记录部署到另外一个文件
,
通过一次写入清除碎片
,
另外一种被称为动态优化是收集无用区域信息并用记录去替换
(
应该是将已经无用的区域进行记录
,
在新插入大小合适的记录时
,
进行重用
)
B+
树数据库
尽管
B+
树数据库比
hash
数据库要慢
,
它的特性是顺序访问每条记录
.
次序可以由用户来指定
, B+
树中的记录是已排序的并且按照逻辑页进行分布
.
通过独立的索引维护每一页使其成为多路平衡树
.
因此检索的时间复杂度是
O(log n),
游标提供对记录的顺序访问
.
游标可以通过指定
key
向前或向后跳跃到指定位置
.
由于每页被安排成双向链表
,
因此时间复杂度为
O(1).
B+
树数据库是基于上面的
hash
数据库实现的
.
由于
B+
树每页的存储相当于
hash
数据库中的记录
, B+
树数据库就继承了
hash
数据库的存储管理效率
.
由于每条记录的头都比较小并且对其方式由每页大小决定
,
所以在大多数情况下
,
数据库文件大小是一个
hash
数据库的一般
.
尽管多个页面的操作需要更新
B+
树
, TC
通过缓存页面和缩减文件操作来加速进行处理
.
在多数情况下由于所有的独立索引都缓存在内存中
,
因此
,
检索一条记录可能需要一次或更少的文件操作
.
B+
树的每一页都是压缩存储的
.
两种压缩方法
: Deflate of ZLIB
和
Block Sorting
of BZIP2
都支持
.
由于一页中的每条记录都有相似的规则
, Lempel-Ziv
或
BWT
算法可以提供很好的压缩效率
.
在处理文本数据时
,
数据库的大小缩减
25%
左右
.
如果数据库太大或硬盘
I/O
造成瓶颈
,
压缩特性会最大限度的提升速度
.
定长数据库
定长数据库限制每个
key
必须是自然数并且值的长度是有限的
,
然而
,
正式由于这种这种约束定长数据库在时间和空间上的效能比其他数据结构都高
.
由于整个数据库的区域都被通过
mmap(
内存映射文件
)
映射在内存作为一个多维数组提交
,
它与文件
I/O
性能关联非常小
.
由于这种简单的结构
,
定长数据库工作要快于
hash
数据库并且它在多线程并发的场合表现非常好
.
数据库的大小与
key
的范围和值的大小限制相关
.
也就是说越小的
key
范围或越小的值长度带来的就是越小的空间占用
.
比如最大
key
为
1000000
值限制大小为
100bytes,
数据库大小就大约为
100MB,
由于记录仅仅被加载到内存
,
因此可以把数据库大小增大到虚拟内存大小
.
Table
数据库
table
数据库并不是直白的简单
key/value
结构
,
而是一个类似关系型数据库的表的结构
.
每条记录通过主键唯一标识并且由多个由字符串命名的列组成值
.
比如
,
一个
”
雇员号
”
唯一确定一个雇员
,
列
”name”, “division”, “salary”
等则用来说明该雇员的其他属性
.
与关系数据库的表不同的是
, table
数据库不需要定义任何的
data schema
并且可以包含与其他记录不同的结构
.
table
数据库支持
query
进行查询
,
不仅仅是主键
,
而是可以通过任意的列作为条件
.
查询条件由列名和条件表达式组成
.
对字符串类型的列还提供了全文匹配
,
向前匹配
,
正则匹配等支持
,
标签搜索和全文检索也被支持
.
在查询中多个条件之间的逻辑交集和并集都是可用的
.
通过指定升序或降序还可以对查询结果集
(
字符串类型或数值类型
)
进行排序
.
你可以在任意列创建索引用于提高搜索和排序的性能
,
尽管列没有数据类型
,
索引却是有类型的
(
只能为
string
和
number
建立
).
倒排索引的空间间隔标记和字符
N-gram
标记也被支持
.
查询优化器会在合适的时候透过每个查询使用索引
,
索引的实现不同于
B+
树数据库的文件
实用功能
数据库在文件系统上的事务机制
.
一次性提交在
beginning
和
end
之间的一系列操作
,
或者中断事务并回退到事务开始之前的状态
.
支持两种级别的事务隔离级别
:
序列化和未提交读
.
TC
提供两种方式的数据库连接
: “reader”
和
”writer”.
作为一个
reader
能够执行检索但不能存储或删除
.
作为一个
writer
则可以执行所有的访问操作
.
通过在连接的时候进行文件锁来处理并发访问
,
当一个
writer
连接到数据库后
,
无论
reader
和
writer
都不允许连接
,
当
reader
连接到数据库时
,
只有
reader
可以连接
.
通过这种方式可以保证在多任务并发时的数据一致性
.
TC
的
api
提供的函数在多线程环境中都是可用的
.
对无关联的数据库对象可以并行操作
,
对于同一个数据库对象的操作
, read-write
锁被用于隔离控制
.
也就是说
,
当一个写线程在操作数据库的时候
,
其他的读线程和写线程都是被锁定的
,
然而
,
当一个读线程在操作数据库的时候
,
读线程是处于非锁定状态的
, hash
数据库和定长数据库的锁粒度是记录级的
,
其他所有的数据库的锁粒度都是整个文件的锁
.
简单但是可扩充的接口
TC
提供了一套简单的基于
OO
设计的
api,
每种数据库操作都被封装
,
公开成为一些简明的方法
,
比如
:
连接
(open),
关闭连接
(disconnect),
插入数据
(put),
删除数据
(out),
检索
(get)
等等
.
由于
B+
树数据库
,
定长数据库
, hash
数据库三种数据库的
api
是非常相似的
,
所以在他们之间进行转换非常容易
.
此外
,
抽象
API
提供了这些数据库的相同处理接口
,
基于抽象
API
的应用可以在运行时决定数据库类型
.
同样提供了工具
API,
比如基本的数据结构
list, map
等都被包含
,
另外还有一些有用的特性
:
内存池
,
字符串处理
,
编码也被包含
.
总共提供了
6
种
C
语言
API,
除
4
种数据库对应的外
,
还有工具
api
和抽象
api.
命令行接口也作为
API
分别提供
,
这些接口对原型构建
,
测试
,
调试很有用
.
除了
C, TC
还提供了
Perl, Ruby, Java,
Lua
的
api,
也希望未来有更多的第三方提供其他语言
API.
在多进程同时访问数据库或远程访问时
, remote service
非常有用
, remote service
由一个数据库服务和它的访问库组成
.
应用程序可以通过远程数据库
api
访问数据库
,
该服务实现了
HTTP
和部分
memcached
协议
,
因此这类协议的产品可以很容易实现切换
.
分享到:
相关推荐
cisco设备配置指导
初级入门吉他谱 guitar tab
c1900-universalk9-npe-mz.SPA.151-2.T0a.bin
c1900-universalk9-mz.SPA.151-4.M4.bin
初级入门吉他谱 guitar tab
linux下Python读取游戏方向盘数据,转换成字符串,通过蓝牙串口发送命令给蓝牙小车。_joysticker_control_serial
python录音机程序1QZQ
c1900-universalk9-npe-mz.SPA.153-1.T.bin
图片+源代码+文本文件
初级入门吉他谱 guitar tab
初级入门吉他谱 guitar tab
linux下的安装命令_linux_install_command
cisco ASA防火墙相关配置
Linux_60个常用命令_linux_60
网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统-网上商城系统 1、资源说明:网上商城系统源码,本资源内项目代码都经过测试运行成功,功能ok的情况下才上传的。 2、适用人群:计算机相关专业(如计算计、信息安全、大数据、人工智能、通信、物联网、自动化、电子信息等)在校学生、专业老师或者企业员工等学习者,作为参考资料,进行参考学习使用。 3、资源用途:本资源具有较高的学习借鉴价值,可以作为“参考资料”,注意不是“定制需求”,代码只能作为学习参考,不能完全复制照搬。需要有一定的基础,能够看懂代码,能够自行调试代码,能够自行添加功能修改代码。 4. 最新计算机软件毕业设计选题大全(文章底部有博主联系方式): https://blog.csdn.net/2301_79206800/article/details/135931154 技术栈、环境、工具、软件: ① 系统环境:Windows ② 开发语言:Java ③ 框架:SpringBoot ④ 架构:B/S、MVC ⑤ 开发环境:IDE
基于ssm的大学生社团管理系统设计与实现.docx
Linux下常用工具及其命令介绍_LinuxTool
基于linux环境下实现了主控端和被控端,主控端像被控端发送控制指令。二者基于TCP协议,通过soc_Shell_RemoteControl
数据集格式:Pascal VOC格式+YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):3135 标注数量(xml文件个数):3135 标注数量(txt文件个数):3135 标注类别数:8 标注类别名称:["crack","dent1","dent2","dislocation","paint_crack","paint_off","scratch","tear"] 每个类别标注的框数: crack 框数 = 205 dent1 框数 = 648 dent2 框数 = 22 dislocation 框数 = 37 paint_crack 框数 = 26 paint_off 框数 = 135 scratch 框数 = 7399 tear 框数 = 257 总框数:8729 使用标注工具:labelImg 标注规则:对类别进行画矩形框 重要说明:暂无 特别声明:本数据集不对训练的模型或者权重文件精度作任何保证,数据集只提供准确且合理标注
c1900-universalk9-mz.SPA.152-4.M6a.bin