倒排与列存

一直傻傻分不清倒排和列存,今天有空梳理一下,主要有四个概念要明确:
  1. 索引方式: 正向索引,反向索引(倒排)
  2. 存储方式: 行存,列存
  3. 数据结构: HashMap,B-Tree,BitMap...
  4. 存储结构: 
    + 顺序组织(顺序文件)
    + 索引组织(索引文件)
    + 散列组织(散列文件)
    + 链组织(多关键字文件)

索引方式

  • 索引方式是种指导性的的思想,和具体数据结构和存储结构没有直接关系
  • 正向索引:DocId->Value
  • 反向索引:Value->DocId

倒排索引 Inverted Index

  • 倒排索引就是反向索引,是信息检索中最基础的索引方法,具体是把索引存为倒排表和倒排链,倒排表存的是所有的值,倒排链存的是 DocId 列表。

存储方式

  • 存储方式就是正排中存value的方式,也是种指导思想,和具体数据结构,存储结构没有关系的
  • 存储方式主要分为按行存储和按列存储(column-oriented)两种

按行存储

  • 以单行作为一个最小存储单元,用偏移量表示各列
  • 没有索引的查询使用大量I/O 
  • Mysql 就是种按行存储的方式,对于无条件的单列取出,需要遍历全表

按列存储

  • 以一列作为一个record,采取对齐的方式或者 MetaData 的方式记录行信息
  • 数据即是索引,只查单列的情况下可以大量降低系统IO 
  • 同种数据在一起,方便压缩
  • HBase 就是按列存储的,采用 MetaData 记录行信息

数据结构

  • 数据结构是数据真实的组织形态,是逻辑层面的真实结构
  • 同一种数据结构可以实现不同的思想,下面以 B-Tree 举例

B-Tree

倒排

  • B 树如果每个内部节点存的是具体的value,叶子节点存 id,那么这就是个倒排
  • 真实场景中,的确有不少搜索引擎是这么存倒排的

正排

  • 如果内部节点存 Id,叶子节点存内容,这就是个正排
  • 真实场景中,mysql 的 pk 索引就是这么存的
  • 行存列存
      + 如果正排的 B-tree 的叶子节点存的是一行的值,那么这就是行存,反之,如果是一列的值,就是列存

存储结构

  • 存储结构就是数据真实落盘的方式,是物理层面的真实结构
  • 根据不同的数据结构有不同的存储结构
  • 一般而言,B-Tree 就是索引文件落盘,而 HashTable 则可以以散列存储。
  • 目前基本都是索引结构落盘,不同产品的具体实现均不相同。
  • 如 IBM 的VSAM就是存储 B-tree 的一种文件格式,由三部分组成:索引集,顺序集和数据集

列存与倒排

  • 回到开头的问题,列存和倒排到底是什么关系呢?
  • 列存是一种正排的存储思想,和倒排没什么关系
  • 一般由于搜索引擎的排序都是少数列的,所以一般搜索引擎都是精确查询用倒排,比较算分用列存

参考资料

  1. 几张图看懂列式存储
  2. 数据结构-文件
  3. 传统的(Oracle)行存储和(HBase)列存储的区别
  4. 二级索引和倒排的区别
  5. 列式存储 HBase 系统架构学习

版权声明

时间: 2024-09-29 05:46:53

倒排与列存的相关文章

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解

搜索引擎里的dictionary data通常存储着这些信息: 索引词(term vocabulary). 文档频率(document frequency,即这个词在多少个文档里出现). 指向倒排表的指针(pointers to each postings list ). 那么,他是怎样的一个数据结构呢? 一种非常naive的词典结构就是: 其中,term的类型是char[20],占20bytes,document frequency类型int,占4-8 bytes,pointer指针占4-8

阿里云HybridDB for PG实践 - 行存、列存,堆表、AO表的原理和选择

标签 PostgreSQL , Greenplum , 向量计算 , 行存储 , 列存 , AO表 背景 Greenplum支持行存和列存,支持堆表和AO表,那么他们有什么不同,如何选择呢? 行存和列存的原理 1.行存,以行为形式组织存储,一行是一个tuple,存在一起.当需要读取某列时,需要将这列前面的所有列都进行deform,所以访问第一列和访问最后一列的成本实际上是不一样的. 在这篇文档中,有deform的详细介绍.<PostgreSQL 向量化执行插件(瓦片式实现) 10x提速OLAP>

HybridDB for PostgreSQL 列存表(AO表)的膨胀、垃圾检查与空间收缩

标签 PostgreSQL , Greenplum , 垃圾检测 , 膨胀 , 列存表 , gp_appendonly_compaction_threshold 背景 Greenplum支持行存储(堆存储)与AO存储,堆存储的垃圾回收和膨胀检测方法请参考: <如何检测.清理Greenplum膨胀.垃圾 - 阿里云HybridDB for PG最佳实践> 对于AO存储,虽然是appendonly,但实际上GP是支持DELETE和UPDATE的,被删除或更新的行,通过BITMAP来标记. AO存储

PostgreSQL 如何让 列存(外部列存) 并行起来

标签 PostgreSQL , 列存 , cstore , append parallel , 继承 背景 PostgreSQL 10已经实现了大部分操作的并行计算,例如(全表扫描,索引扫描,位图扫描,哈希JOIN,哈希聚合,分组聚合,排序,建索引等). 对于外部表,要实现并行扫描,PostgreSQL有什么方法呢? PostgreSQL不仅支持单个对象的并行计算,还支持多个对象的并行访问.多个对象的并行访问,包括继承表.分区表.继承外部表.UNION.UNION ALL等语义. 这个patch

MySQL · 引擎特性 · Infobright 列存数据库

简介 系统架构 存储引擎 优化器和执行器 数据装载和卸载 领域知识 查询优化 简单场景的示例 小结 存储结构 Data Pack Knowledge Node 数据压缩 总结 简介 Infobright 是一个面向 OLAP 场景的开源列存数据库.比较容易找到代码的版本是 Infobright Community Edition 4.0.7,大概是 2006 年前后的代码.2016 年6 月,Infobright 决定停止开源1.由于它同时提供企业版和社区版,开源版本的功能相比企业版而言,肯定是

行存、列存,堆表、AO表性能对比 - 阿里云HDB for PostgreSQL最佳实践

标签 PostgreSQL , GIS , PostGIS , Greenplum , 空间检索 , GiST , B-Tree , geohash 背景 <Greenplum 行存.列存,堆表.AO表的原理和选择> 以上文档详细的介绍了行存.列存,堆表.AO表的原理以及选择的依据. <一个简单算法可以帮助物联网,金融 用户 节约98%的数据存储成本 (PostgreSQL,Greenplum帮你做到)> 以上文档介绍了提升基于列存的全局数据压缩比的方法. <解密上帝之手 -

Greenplum列存压缩表原理

用法 create table testao(id int, name text) with (APPENDONLY=true, ORIENTATION=column, COMPRESSTYPE=zlib, COMPRESSLEVEL=5, BLOCKSIZE=1048576, OIDS=false) APPENDONLY=true, ORIENTATION=column这两个属性决定了这是列存压缩表. COMPRESSTYPE: 压缩方式,支持zlip,RTE等 COMPRESSLEVEL:

Greenplum行存与列存的选择以及转换方法

背景 数据在数据库中的存储形式多种多样,比较常见的如 1. PostgreSQL的堆表,以行的形式存储,(当变成字段压缩后的长度超过数据块的四分之一时,会以TOAST的形式存储到TOAST表). 2. MySQL innodb则是以b+tree形式存储的. 在数据仓库产品中,如Greenplum,支持行存,也支持列存. 还有很多存储格式,本文将讨论行存和列存应该如何选择呢? 行存储优劣分析 Greenplum行存储(堆表)的优势在哪里? 数据顺序写入BLOCK中,持续写入的情况下,一条记录命中在

什么是倒排索引?倒排表?如何建立倒排索引?

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 为什么我们要说倒排索引呢?      因为倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式.也是搜索引擎的核心内容!     在搜索引擎实际的引用之中,有时需要按照关键字的某些值 查找记录,所以我们是按照关键字建立索引,这个索引我们就称之为: 倒排索引, 而带有倒排索引的文件我们又称作: 倒排索引文件 也可以叫它为: 倒排文件 来实现