绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
BitSet索引学习
2020-06-03 13:39:35

近我们在使用druid的过程中使用了BitSet索引。这个邮件是我之前总结的JDK的BitSet实现。非常巧妙。我在这里可以进一步分享一下。


目录

一.总结一下JDK的BitSet

二.Roaring BitSet

三.留些思考问题

四.我的要求


一.总结一下JDK的BitSet

1.long是8个字节,也就是64bit。64个bit可以保存64个数字。

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 表示0

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 表示1

依次类推

2.我们可以将数字[0,n)划分成为

[0,64),[64,2*64),[2*64,3*64).....

这样使用一个long[]数组就能够表示是否存在某个数字。

比如 8 我们可以放在long[0]这个long,使用bit

00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 表示8


二.Roaring BitSet

roaring bitset 是JDK BitSet的升级版本。他考虑了数据的稀疏和稠密这两种情况,采用了灵活的数据结构,来降低内存使用。同时,他也考虑了CPU的缓存,使用佳的内存大小来存储数据。这两方面的优化,让BitSet存储下降,同时运算能力提升。


1.short是2个字节,也就是16bit,long是8个字节,也就是64bit。

2.我们可以将数字[0,n)划分成为

[0,2^16),[2^16,2*2^16),[2*2^16,3*2^16)...

3.对于一个32bit的数字,我们可以将其分为高16位和后16位两部分。相同高位的数据保存在同一个container里面。

4.container会根据数据的稀疏还是稠密选择不一样的数据结构。

当相同高位数据对应的container保存的数据少于4096个时,container采用 short[]数组进行数据的保存,当数据超过4096后采用BitMapContainer进行保存。

bitmapcontainer的数据结构是 long[]数据,他的长度是固定的,1024。1024个long就能保存1024*64个关键字,其大小正好是8 kb。


当同一个高16位key对应的数据少于4096时


当保存的数据超过4096时



三.留些思考问题

1.当存储1~65536个数据时,是JDK的BitSet省内存还是Roaring BitSet省内存?请评估内存占用量。

2.当存储1~10000000000个数据中的随机数据,随机数据取1000000个时,JDK BitSet和Roaring BitSet那个性能更佳?请评估内存占用量。

这些问题需要思考,我还要求要对RLE类型BitMap有深入理解。我不希望只知道写的慢,或者程序告诉我们的,这个数据结构存了什么数据,然后他占用了多少内存。我希望我们能算出来。

四.我的要求

我们是在做大数据。我们要对内存敏感。同时我们要对数据的规律敏感。我们必须要掌握核心技能,才能做到了然于胸。

分享好友

分享这个小栈给你的朋友们,一起进步吧。

Elasticsearch
创建时间:2020-05-22 14:49:51
ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsearch是用Java开发的,并作为Apache许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。我们建立一个网站或应用程序,并要添加搜索功能,但是想要完成搜索工作的创建是非常困难的。我们希望搜索解决方案要运行速度快,我们希望能有一个零配置和一个完全免费的搜索模式,我们希望能够简单地使用JSON通过HTTP来索引数据,我们希望我们的搜索服务器始终可用,我们希望能够从一台开始并扩展到数百台,我们要实时搜索,我们要简单的多租户,我们希望建立一个云的解决方案。因此我们利用Elasticsearch来解决所有这些问题及可能出现的更多其它问题。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

技术专家

查看更多
  • 栈栈
    专家
戳我,来吐槽~