使用bitset实现毫秒级查询(实例讲解)
前言
因为业务要求api的一次请求响应时间在10ms以内，所以传统的数据库查询操作直接被排除(网络io和磁盘io)。通过调研，最终使用了bieset,目前已经正常运行了很久
bitset介绍
看JDK中的解释简直一头雾水，用我自己的理解概括一下
1.bitset的内部实现是long数组
2.set中每一个位的默认值为false（0）
3.bitset长度按需增长
4.bitset非线程安全
bitset关键方法分析
/**
*Setsthebitatthespecifiedindexto{@codetrue}.
*
*@parambitIndexabitindex
*@throwsIndexOutOfBoundsExceptionifthespecifiedindexisnegative
*@sinceJDK1.0
*/
publicvoidset(intbitIndex){
if(bitIndex<0)
thrownewIndexOutOfBoundsException("bitIndex<0:"+bitIndex);
intwordIndex=wordIndex(bitIndex);
expandTo(wordIndex);
words[wordIndex]|=(1L<
设置指定“位”为true，bitIndex参数为非负整数。假设我们执行以下代码,观察上面代码中worIndex，words[wordIndex]值的变化
BitSetbs=newBitSet()
bs.set(0);
bs.set(1);
bs.set(2);
bs.set(3);
bs.set(4);
bitIndex
wordIndex
words[wordIndex]
words[wordIndex]二进制表示
0
0
1
0001
1
0
3
0011
2
0
7
0111
3
0
15
1111
4
0
31
00011111
通过上表，我们可以很清晰的根据bitIndex和words[wordIndex]二进制值的对应关系，得到一个结论，即：bitset中每一个long可以表示64个非负整数在bitSet中存在与否。例如：0001可以表示整数0在bitset中存在，1111可以表示整数3,2,1,0在bitset中存在。
进入正题，实现bitset毫秒级查询
想象一个场景，我们有一张user表
CREATETABLE`user`(
`id`int(11)NOTNULLAUTO_INCREMENT,
`name`varchar(255)NOTNULL,
`address`varchar(255)NOTNULLcomment'地址',
`gender`varchar(10)NOTNULLcomment'性别',
`age`varchar(10)NOTNULL,
PRIMARYKEY(`uid`)
)ENGINE=InnoDBAUTO_INCREMENT=0DEFAULTCHARSET=utf8;
假设我们要查询“北京市18岁的女生”，那么对应的sql如下：
select*from`user`whereaddress='北京'andage='18'andgender='girl';
如何使用bitset实现同样的查询呢？
1.将user表数据加载进内存中
2.为user表建立address,age,gender维度的bitset索引
3.根据索引查询数据
1.将user表数据加载进内存中
将user表从数据库读取出来存入List
User实体类：
publicclassUserimplementsCloneable{
privateStringname;
privateStringaddress;
privateStringgender;
privateStringage;
@Override
publicStringtoString(){
return"User[name="+name+",address="+address+",gender="+gender+",age="+age+"]";
}
@Override
publicUserclone(){
Useruser=null;
try{
user=(User)super.clone();
}catch(CloneNotSupportedExceptione){
e.printStackTrace();
}
returnuser;
}
//省略getset方法。。。
2.建立索引
创建bitset索引模型类
publicclassBitSetIndexModel{
privateStringtype;//索引类型：address，age，gender
privateConcurrentHashMapmap;//索引类型和bitSet在bsList中下标的映射关系
privateListlist;//索引类型的值集合，例如gender：girl，boy
privateListbsList;//bitset集合
publicBitSetIndex(){
}
publicBitSetIndexModel(Stringtype){
this.type=type;
map=newConcurrentHashMap();
list=newArrayList();
bsList=newArrayList();
}
publicStringgetType(){
returntype;
}
publicvoidsetType(Stringtype){
this.type=type;
}
publicMapgetMap(){
returnmap;
}
publicvoidsetMap(ConcurrentHashMapmap){
this.map=map;
}
publicListgetList(){
returnlist;
}
publicvoidsetList(Listlist){
this.list=list;
}
publicListgetBsList(){
returnbsList;
}
publicvoidsetBsList(ListbsList){
this.bsList=bsList;
}
/**
*
*@paramstr
*@parami
*/
publicvoidcreateIndex(Stringstr,inti){
BitSetbitset=null;
//获取‘str'对应的bitset在bsList中的下标
Integerindex=this.getMap().get(str);
if(index!=null){
bitset=this.getBsList().get(index);
if(bitset==null){
bitset=newBitSet();
this.getBsList().add(index,bitset);
}
bitset.set(i,true);//将str对应的位置为true,true可省略
}else{
bitset=newBitSet();
Listlist=this.getList();
list.add(str);
index=list.size()-1;
bitset.set(i,true);
this.getBsList().add(bitset);
this.getMap().put(str,index);
}
}
/**
*从entity里拿出符合条件的bitset
*
*@paramstr
*@return
*/
publicBitSetget(Stringstr){
BitSetbitset=null;
str=str.toLowerCase();
Integerindex=this.getMap().get(str);
if(index!=null){
bitset=this.getBsList().get(index);
}else{
bitset=newBitSet();
}
returnbitset;
}
/**
*bitset的与运算
*
*@paramstr
*@parambitset
*@return
*/
publicBitSetand(Stringstr,BitSetbitset){
if(str!=null){
str=str.toLowerCase();
if(bitset!=null){
bitset.and(get(str));
}else{
bitset=newBitSet();
bitset.or(get(str));
}
}
returnbitset;
}
/**
*bitset的或运算
*
*@paramstr
*@parambitset
*@return
*/
publicBitSetor(Stringstr,BitSetbitset){
if(str!=null){
str=str.toLowerCase();
if(bitset!=null){
bitset.or(get(str));
}else{
bitset=newBitSet();
bitset.or(get(str));
}
}
returnbitset;
}
/**
*获取bitset值为true的即把bitset翻译为list的索引
*
*@parambitset
*@return
*/
publicstaticListgetRealIndexs(BitSetbitset){
Listindexs=newArrayList();
if(bitset!=null){
inti=bitset.nextSetBit(0);
if(i!=-1){
indexs.add(i);
for(i=bitset.nextSetBit(i+1);i>=0;i=bitset.nextSetBit(i+1)){
intendOfRun=bitset.nextClearBit(i);
do{
indexs.add(i);
}while(++i
为每一个user对象创建address,gender,age维度索引
publicclassUserIndexStore{
privatestaticfinalStringADDRESS="address";
privatestaticfinalStringGENDER="gender";
privatestaticfinalStringAGE="age";
privateBitSetIndexModeladdress;
privateBitSetIndexModelgender;
privateBitSetIndexModelage;
privateConcurrentHashMapuserMap;//存储所有的user数据
publicstaticfinalUserIndexStoreINSTANCE=getInstance();
privateUserIndexStore(){
init();
}
publicstaticUserIndexStoregetInstance(){
returnUserIndexStoreHolder.instance;
}
privatestaticclassUserIndexStoreHolder{
privatestaticUserIndexStoreinstance=newUserIndexStore();
}
privatevoidinit(){
this.address=newBitSetIndexModel(ADDRESS);
this.gender=newBitSetIndexModel(GENDER);
this.age=newBitSetIndexModel(AGE);
userMap=newConcurrentHashMap();
}
/**
*构建索引
*@paramusers
*/
publicvoidcreateIndex(Listusers){
if(users!=null&&users.size()>0){
for(intindex=0;index
3.测试bitset
publicclassBitSetTest{
publicstaticvoidmain(String[]args){
Listusers=buildData();
UserIndexStore.getInstance().createIndex(users);
ExecutorServiceexecutorService=Executors.newFixedThreadPool(20);
intnum=2000;
longbegin1=System.currentTimeMillis();
for(inti=0;iindexs=BitSetIndexModel.getRealIndexs(UserIndexStore.getInstance().query("北京","girl","18"));
for(Integerindex:indexs){
UserIndexStore.getInstance().findUser(index);
}
}
};
executorService.execute(syncRunnable);
}
executorService.shutdown();
while(true){
try{
if(executorService.awaitTermination(1,TimeUnit.SECONDS)){
System.out.println("单次查询时间为："+(System.currentTimeMillis()-begin1)/num+"ms");
break;
}
}catch(InterruptedExceptione){
e.printStackTrace();
}
}
}
privatestaticListbuildData(){
String[]addresss={"北京","上海","深圳"};
String[]ages={"16","17","18"};
Listusers=newArrayList<>();
for(inti=0;i<200000;i++){
Useruser=newUser();
user.setName("name"+i);
intrand=ThreadLocalRandom.current().nextInt(3);
user.setAddress(addresss[ThreadLocalRandom.current().nextInt(3)]);
user.setGender((rand&1)==0?"girl":"boy");
user.setAge(ages[ThreadLocalRandom.current().nextInt(3)]);
users.add(user);
}
returnusers;
}
}
测试结果(查询2w次)：
数据量（users.size()）|并发数|平均查询时间
---|---|---
20w|10|1ms
50w|20|3ms
100w|50|9ms
测试机为thinkpadx240i58g内存
4.总结
==优点==：
通过测试发现随着数据量的增大和并发数的提高，平均耗时并没有明显升高，并且响应时间都在10ms以内
==缺点==：
1.不适合数据量太大的情况,因为需要把数据全部加载进内存
2.不适合复杂查询
3.不适合对name,id等唯一值做查询
后记
因为我们的查询业务比较简单，唯一的要求是速度，并且数据量也不大，每张表的数据量都不超过100w，所以使用这种方式比较合适。
在本篇文章中只谈到了如何创建索引，以及最基本的查询，在下一篇中我会继续说明如何更新索引，以及一些复杂查询，比如<,>,betweenand。
以上这篇使用bitset实现毫秒级查询(实例讲解)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。