以mysql为例详解ToplingDB 的 UintIndex

目录
  • 前言
  • 以 MySQL 为例
  • 应用到 MongoDB
  • 压缩率 & 性能

前言

在 ToplingDB 的 CO-Index(Compressed Ordered Index) 家族中，Nest Succinct Trie 是最通用的。但是，伴随通用的，往往是低效。我们针对一些特殊场景，采用了特殊的实现，用以提高性能……

这里面，最特殊的一类 Index，就是 UintIndex，顾名思义，就是 Key 为 unsigned int 时的 index。

以 MySQL 为例

在 MySQL 中，我们往往会建立这样一个表：

CREATE TABLE Student(
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(255) INDEX,
    dorm_id INT INDEX,
    -- others ...
);

这里的 PRIMARY KEY 最终体现到 MyRocks，是这样的形式：

PrefixID id

通过配置，我们可以通过 keyPrefixLen 将 PrefixID 分离出去，这样，Index 中就只剩下一个 id 字段了，并且，在 SST 中，这些 id 往往都是比较紧密的范围（被删除的 id 是范围中的空洞），比如，在某个 SST 中，存储的 id 范围是 1,000,000~2,000,000。

并且，我们知道，CO-Index 会将用户 Key(在这里就是 id 字段) 映射到一个 内部ID，再用这个 内部ID 去访问 PA-Zip……

在一个 SST 中，把这一切串起来，我们就能使用简单且高效的方式来实现 Index 了：

图中的 ValueOrd 就是前面说的 内部ID，Index 共有 108 个 Key，BitMap 中有 MaxKey - MinKey + 1 = 229 个 Bit。

  • 如果这个范围中，一个空洞也没有，那么，Index 中我们只需要保存 id 的最大最小值。

    • 内部ID = Student.id - MinStudentID
  • 如果这个范围中，只有极少数的空洞，那么，Index 中我们只需要保存那些空洞 中的 id。
    • 内部ID = Student.id - (Hole num before this Student.id)
  • 如果这个范围中，有相当数量的空洞，那么，Index 中我们只需要保存一个 BitMap，其中相应 bit 的含义是这个 id 是否存在。
    • 利用 Rank-Select 的思想：内部ID = BitMap.rank1(id)

进一步，在概念上，如果我们把 一个空洞也没有 和 只有极少数的空洞 也用 Rank-Select 来表达：

那么，这三种情况，在形式上就可以统一起来！实际上，在代码实现中，这三种不同的 Rank-Select 实现是作为模板类 UintIndex 的模板参数的，在保持抽象的同时，又不损失性能。

应用到 MongoDB

在 MongoDB 中，也存在类似 MySQL Student.id 这样的东西：

MongoDB 有两大类 Key Value 数据，RecordStore（即 Collection） 和 Index：

这样，MongoDB 的 RecordStore 也可以利用 UintIndex

压缩率 & 性能

压缩率自然不用说，UintIndexAllOne 的压缩率接近于无穷大，压缩率最差的 UintIndexBitMap，其压缩率也在 30 倍以上！

性能，最关键的是性能，相比传统的块压缩，Nest Succinct Trie 最大的性能劣势在于顺序扫描（从头至尾顺序扫描，定位到某个点然后接着顺序扫描），因为对于 Nest Succinct Trie，即便是顺序扫描，它的计算也很复杂，并且内存访问非常随机。而对于 UintIndex，事情就简单多了，比 Nest Succinct Trie 会快 100 倍以上，而其中占比最大的性能开销，实际上是函数调用本身！

到此这篇关于以mysql为例详解ToplingDB 的 UintIndex的文章就介绍到这了,更多相关mysql UintIndex内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Ubuntu 服务器安装 MySQL 远程数据库的方法

    Ubuntu 服务器安装 MySQL 远程数据库的方法

    目录 在 Ubuntu 上安装 MySQL 开启远程连接权限 编辑 MySQL 配置文件 创建 MySQL 用户 远程连接 MySQL 数据库 命令行远程访问 Jetbrains 家族 Database 连接 在 Web 项目中,我们需要使用到远程数据库,开发阶段也需要连接并查看数据库的状况.腾讯云.阿里云等云平台提供了远程数据库,可直接使用:当然也可以自己在部署 Web 的服务器上安装数据库,将其配置为远程数据库,供 Web 应用使用. 本篇介绍如何在 Linux 服务器上安装 MySQL 数

  • MySQL中的insert set 和 insert values用法

    目录 insert set 和 insert values用法 insert values insert set mysql 语法 insert into set insert set 和 insert values用法 insert values 优点:可以批量插入: 缺点:单条执行效率低.<适合批量插入> insert into table(col1,col2,col3) values('val1','val2','val3'); insert set 优点:执行效率高: 缺点:每次只能插

  • MySQL中的insert ignore into使用

    MySQL中的insert ignore into使用

    目录 MySQL中的insert ignore into 1.插入的数据是主键冲突时 2.没有主键冲突时,直接插入数据 insert ignore into--跳坑 MySQL中的insert ignore into 最近工作中,使用到了insert ignore into语法,感觉这个语法还是挺有用的,就记录下来做个总结. insert ignore into : 忽略重复的记录,直接插入数据. 包括两种场景: 1.插入的数据是主键冲突时 insert ignore into会给出warnin

  • 以mysql为例详解ToplingDB 的 UintIndex

    以mysql为例详解ToplingDB 的 UintIndex

    目录 前言 以 MySQL 为例 应用到 MongoDB 压缩率 & 性能 前言 在 ToplingDB 的 CO-Index(Compressed Ordered Index) 家族中,Nest Succinct Trie 是最通用的.但是,伴随通用的,往往是低效.我们针对一些特殊场景,采用了特殊的实现,用以提高性能…… 这里面,最特殊的一类 Index,就是 UintIndex,顾名思义,就是 Key 为 unsigned int 时的 index. 以 MySQL 为例 在 MySQL 中

  • mysql分区功能详解,以及实例分析

    一,什么是数据库分区 前段时间写过一篇关于mysql分表的 的文章,下面来说一下什么是数据库分区,以mysql为例.mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面 (可以通过my.cnf中的datadir来查看),一张表主要对应着三个文件,一个是frm存放表结构的,一个是myd存放表数据的,一个是myi存表 索引的.如果一张表的数据量太大的话,那么myd,myi就会变的很大,查找数据就会变的很慢,这个时候我们可以利用mysql的分区功能,在物理上将这 一张

  • Linux中对MySQL优化实例详解

    Linux中对MySQL优化实例详解 vim /etc/my.cnf以下只列出my.cnf文件中[mysqld]段落中的内容,其他段落内容对MySQL运行性能影响甚微,因而姑且忽略. [mysqld] port = 3306 serverid = 1 socket = /tmp/mysql.sock skip-locking 避免MySQL的外部锁定,减少出错几率增强稳定性. skip-name-resolve 禁止MySQL对外部连接进行DNS解析,使用这一选项可以消除MySQL进行DNS解析

  • MySQL 权限控制详解

    mysql权限控制 作为一名DBA,想必大家对MySQL中的权限都不陌生,MySQL中对于权限的控制分为三个层面: 全局性的管理权限,作用于整个MySQL实例级别 数据库级别的权限,作用于某个指定的数据库上或者所有的数据库上 数据库对象级别的权限,作用于指定的数据库对象上(表.视图等)或 者所有的数据库对象上 这里,我们将mysql中的所有权限列出来,最后给出一个特殊的案例来反应mysql权限控制中的一个小bug.首先来看权限列表,权限的顺序按照首字母的顺序进行排列: •All/All Priv

  • MYSQL存储过程 注释详解

    MYSQL存储过程 注释详解

    目录 1.使用说明 2.准备 3.语法 3.1 变量及赋值 3.2 入参出参 3.3 流程控制-判断 3.4 流程控制-循环 3.5 流程控制-退出.继续循环 3.6 游标 3.7 存储过程中的handler 4.练习 4.1 利用存储过程更新数据 4.3 其他场景: 5.其他 5.1 characteristic 5.2 死循环处理 5.3 可以在select语句中写case 5.4 临时表 0.环境说明: 软件 版本 mysql 8.0 navicat 1.使用说明 存储过程时数据库的一个重

  • Struts中的Action 单例与多例详解

     Struts中的Action 单例与多例详解 struts2中action是多例的,即每次访问网络地址的时候都会产生一个action public class pr_action { public pr_action(){ System.out.println("创建action成功!!!"); } public void execute(){ } } 运行代码可以看到,每次访问该网络地址都会在控制台输出一次!!! 如果是单例的话,若出现两个用户都修改一个对象的属性值,则会因为用户修

  • 微信小程序开发图片拖拽实例详解

    微信小程序开发图片拖拽实例详解

    微信小程序开发图片拖拽实例详解 1.编写页面结构:moveimg.wxml <view class="container"> <view class="cnt"> <image class="image-style" src="../uploads/foods.jpg" style="left:{{ballleft}}px;width:{{screenWidth}}px" bi

  • Oracle10个分区和Mysql分区区别详解

    Oracle10g分区常用的是:range(范围分区).list(列表分区).hash(哈希分区).range-hash(范围-哈希分区).range-list(列表-复合分区). Range分区:Range分区是应用范围比较广的表分区方式,它是以列的值的范围来做为分区的划分条件,将记录存放到列值所在的range分区中. 如按照时间划分,2010年1月的数据放到a分区,2月的数据放到b分区,在创建的时候,需要指定基于的列,以及分区的范围值. 在按时间分区时,如果某些记录暂无法预测范围,可以创建m

  • MySQL 序列 AUTO_INCREMENT详解及实例代码

    MySQL 序列 AUTO_INCREMENT详解及实例代码 MySQL序列是一组整数:1, 2, 3, ...,由于一张数据表只能有一个字段自增主键, 如果你想实现其他字段也实现自动增加,就可以使用MySQL序列来实现. 本章我们将介绍如何使用MySQL的序列. 使用AUTO_INCREMENT MySQL中最简单使用序列的方法就是使用 MySQL AUTO_INCREMENT 来定义列. 实例 以下实例中创建了数据表insect, insect中id无需指定值可实现自动增长. mysql>

  • MySQL prepare原理详解

    Prepare的好处  Prepare SQL产生的原因.首先从mysql服务器执行sql的过程开始讲起,SQL执行过程包括以下阶段 词法分析->语法分析->语义分析->执行计划优化->执行.词法分析->语法分析这两个阶段我们称之为硬解析.词法分析识别sql中每个词,语法分析解析SQL语句是否符合sql语法,并得到一棵语法树(Lex).对于只是参数不同,其他均相同的sql,它们执行时间不同但硬解析的时间是相同的.而同一SQL随着查询数据的变化,多次查询执行时间可能不同,但硬解

随机推荐