使用bitset实现毫秒级查询(实例讲解)

前言

因为业务要求api的一次请求响应时间在10ms以内,所以传统的数据库查询操作直接被排除(网络io和磁盘io)。通过调研,最终使用了bieset,目前已经正常运行了很久

bitset介绍

看JDK中的解释简直一头雾水,用我自己的理解概括一下

1.bitset的内部实现是long数组
2.set中每一个位的默认值为false(0)
3.bitset长度按需增长
4.bitset非线程安全

bitset关键方法分析

/**
 * Sets the bit at the specified index to {@code true}.
 *
 * @param bitIndex a bit index
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since JDK1.0
 */
public void set(int bitIndex) {
 if (bitIndex < 0)
  throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

 int wordIndex = wordIndex(bitIndex);
 expandTo(wordIndex);

 words[wordIndex] |= (1L << bitIndex); // Restores invariants

 checkInvariants();
}

设置指定“位”为true,bitIndex参数为非负整数。假设我们执行以下代码,观察上面代码中worIndex,words[wordIndex]值的变化

BitSet bs = new BitSet()
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 0001 1111

通过上表,我们可以很清晰的根据bitIndex和words[wordIndex]二进制值的对应关系,得到一个结论,即:bitset中每一个long可以表示64个非负整数在bitSet中存在与否。例如:0001可以表示整数0在bitset中存在,1111可以表示整数3,2,1,0在bitset中存在。

进入正题,实现bitset毫秒级查询

想象一个场景,我们有一张user表

CREATE TABLE `user` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(255) NOT NULL,
 `address` varchar(255) NOT NULL comment '地址',
 `gender` varchar(10) NOT NULL comment '性别',
 `age` varchar(10) NOT NULL,
 PRIMARY KEY (`uid`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8;

假设我们要查询“北京市18岁的女生”,那么对应的sql如下:

select * from `user` where address='北京' and age='18' and gender='girl';

如何使用bitset实现同样的查询呢?

1.将user表数据加载进内存中

2.为user表建立address,age,gender维度的bitset索引

3.根据索引查询数据

1.将user表数据加载进内存中

将user表从数据库读取出来存入List

User实体类:

public class User implements Cloneable {
 private String name;
 private String address;
 private String gender;
 private String age;

 @Override
 public String toString() {
  return "User [name=" + name + ", address=" + address + ", gender=" + gender + ", age=" + age + "]";
 }

 @Override
 public User clone() {
  User user = null;
  try {
   user = (User) super.clone();
  } catch (CloneNotSupportedException e) {
   e.printStackTrace();
  }
  return user;
 }
 //省略get set 方法。。。

2.建立索引

创建bitset索引模型类

public class BitSetIndexModel {
 private String type;//索引类型:address,age,gender
 private ConcurrentHashMap<String, Integer> map;//索引类型和bitSet在bsList中下标的映射关系
 private List<String> list;//索引类型的值集合,例如gender:girl,boy
 private List<BitSet> bsList;//bitset集合

 public BitSetIndex() {

 }

 public BitSetIndexModel(String type) {
  this.type = type;
  map = new ConcurrentHashMap<String, Integer>();
  list = new ArrayList<String>();
  bsList = new ArrayList<BitSet>();
 }

 public String getType() {
  return type;
 }

 public void setType(String type) {
  this.type = type;
 }

 public Map<String, Integer> getMap() {
  return map;
 }

 public void setMap(ConcurrentHashMap<String, Integer> map) {
  this.map = map;
 }

 public List<String> getList() {
  return list;
 }

 public void setList(List<String> list) {
  this.list = list;
 }

 public List<BitSet> getBsList() {
  return bsList;
 }

 public void setBsList(List<BitSet> bsList) {
  this.bsList = bsList;
 }

 /**
  *
  * @param str
  * @param i
  */
 public void createIndex(String str, int i) {
  BitSet bitset = null;
  //获取‘str'对应的bitset在bsList中的下标
  Integer index = this.getMap().get(str);
  if (index != null) {
   bitset = this.getBsList().get(index);
   if (bitset == null) {
    bitset = new BitSet();
    this.getBsList().add(index, bitset);
   }
   bitset.set(i, true);// 将str对应的位置为true,true可省略
  } else {
   bitset = new BitSet();
   List<String> list = this.getList();
   list.add(str);
   index = list.size() - 1;
   bitset.set(i, true);
   this.getBsList().add(bitset);
   this.getMap().put(str, index);
  }
 }

 /**
  * 从entity里拿出符合条件的bitset
  *
  * @param str
  * @return
  */
 public BitSet get(String str) {
  BitSet bitset = null;
  str = str.toLowerCase();
  Integer index = this.getMap().get(str);

  if (index != null) {
   bitset = this.getBsList().get(index);
  } else {
   bitset = new BitSet();
  }
  return bitset;
 }

 /**
  * bitset的与运算
  *
  * @param str
  * @param bitset
  * @return
  */
 public BitSet and(String str, BitSet bitset) {
  if (str != null) {
   str = str.toLowerCase();
   if (bitset != null) {
    bitset.and(get(str));
   } else {
    bitset = new BitSet();
    bitset.or(get(str));
   }
  }
  return bitset;
 }

 /**
  * bitset的或运算
  *
  * @param str
  * @param bitset
  * @return
  */
 public BitSet or(String str, BitSet bitset) {
  if (str != null) {
   str = str.toLowerCase();
   if (bitset != null) {
    bitset.or(get(str));
   } else {
    bitset = new BitSet();
    bitset.or(get(str));
   }
  }
  return bitset;
 }

 /**
  * 获取bitset值为true的 即 把 bitset翻译为list的索引
  *
  * @param bitset
  * @return
  */
 public static List<Integer> getRealIndexs(BitSet bitset) {
  List<Integer> indexs = new ArrayList<Integer>();
  if (bitset != null) {
   int i = bitset.nextSetBit(0);
   if (i != -1) {
    indexs.add(i);
    for (i = bitset.nextSetBit(i + 1); i >= 0; i = bitset.nextSetBit(i + 1)) {
     int endOfRun = bitset.nextClearBit(i);
     do {
      indexs.add(i);
     } while (++i < endOfRun);
    }
   }
  }

  return indexs;
 }

}

为每一个user对象创建address,gender,age维度索引

public class UserIndexStore {

 private static final String ADDRESS = "address";
 private static final String GENDER = "gender";
 private static final String AGE = "age";
 private BitSetIndexModel address;
 private BitSetIndexModel gender;
 private BitSetIndexModel age;
 private ConcurrentHashMap<Integer, User> userMap;//存储所有的user数据

 public static final UserIndexStore INSTANCE = getInstance();

 private UserIndexStore() {
  init();
 }

 public static UserIndexStore getInstance() {
  return UserIndexStoreHolder.instance;
 }

 private static class UserIndexStoreHolder {
  private static UserIndexStore instance = new UserIndexStore();
 }

 private void init() {
  this.address = new BitSetIndexModel(ADDRESS);
  this.gender = new BitSetIndexModel(GENDER);
  this.age = new BitSetIndexModel(AGE);
  userMap = new ConcurrentHashMap<Integer, User>();
 }

 /**
  * 构建索引
  * @param users
  */
 public void createIndex(List<User> users) {
  if (users != null && users.size() > 0) {
   for (int index = 0; index < users.size(); index++) {
    User user = users.get(index);
    getAddress().update(user.getAddress(), index);
    getGender().update(user.getGender(), index);
    getAge().update(user.getAge(), index);
    this.userMap.put(index, user);
   }
  }
 }

 public BitSet query(String address, String gender, String age) {
  BitSet bitset = null;
  bitset = getAddress().and(address, bitset);
  bitset = getGender().and(gender, bitset);
  bitset = getAge().and(age, bitset);
  return bitset;
 }

 public User findUser(Integer index) {
  User user = this.userMap.get(index);
  if (user != null) {
   return user.clone();//可能会对user做修改操作,要保证内存原始数据不变
  }
  return null;
 }

 public BitSetIndexModel getAddress() {
  return address;
 }

 public void setAddress(BitSetIndexModel address) {
  this.address = address;
 }

 public BitSetIndexModel getGender() {
  return gender;
 }

 public void setGender(BitSetIndexModel gender) {
  this.gender = gender;
 }

 public BitSetIndexModel getAge() {
  return age;
 }

 public void setAge(BitSetIndexModel age) {
  this.age = age;
 }

}

3.测试bitset

public class BitSetTest {

 public static void main(String[] args) {
  List<User> users = buildData();
  UserIndexStore.getInstance().createIndex(users);
  ExecutorService executorService = Executors.newFixedThreadPool(20);
  int num = 2000;
  long begin1 = System.currentTimeMillis();
  for (int i = 0; i < num; i++) {
   Runnable syncRunnable = new Runnable() {
    @Override
    public void run() {
     List<Integer> indexs = BitSetIndexModel.getRealIndexs(UserIndexStore.getInstance().query("北京", "girl", "18"));
     for (Integer index : 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 (InterruptedException e) {
    e.printStackTrace();
   }
  }
 }

 private static List<User> buildData() {
  String[] addresss = { "北京", "上海", "深圳" };
  String[] ages = { "16", "17", "18" };
  List<User> users = new ArrayList<>();
  for (int i = 0; i < 200000; i++) {
   User user = new User();
   user.setName("name" + i);
   int rand = 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);
  }
  return users;
 }

}

测试结果(查询2w次):

数据量(users.size()) | 并发数 | 平均查询时间

---|---|---
20w | 10 | 1ms
50w | 20 | 3ms
100w| 50 | 9ms

测试机为thinkpad x240 i5 8g内存

4.总结

==优点==:

通过测试发现随着数据量的增大和并发数的提高,平均耗时并没有明显升高,并且响应时间都在10ms以内

==缺点==:

1.不适合数据量太大的情况,因为需要把数据全部加载进内存

2.不适合复杂查询

3.不适合对name,id等唯一值做查询

后记

因为我们的查询业务比较简单,唯一的要求是速度,并且数据量也不大,每张表的数据量都不超过100w,所以使用这种方式比较合适。

在本篇文章中只谈到了如何创建索引,以及最基本的查询,在下一篇中我会继续说明如何更新索引,以及一些复杂查询,比如<,>,between and。

以上这篇使用bitset实现毫秒级查询(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 使用bitset实现毫秒级查询(实例讲解)

    前言 因为业务要求api的一次请求响应时间在10ms以内,所以传统的数据库查询操作直接被排除(网络io和磁盘io).通过调研,最终使用了bieset,目前已经正常运行了很久 bitset介绍 看JDK中的解释简直一头雾水,用我自己的理解概括一下 1.bitset的内部实现是long数组 2.set中每一个位的默认值为false(0) 3.bitset长度按需增长 4.bitset非线程安全 bitset关键方法分析 /** * Sets the bit at the specified inde

  • php生成毫秒时间戳的实例讲解

    php时间函数time()生成当前时间的秒数,但是在一些情况下我们需要获取当前服务器时间和GMT(格林威治时间)1970年1月0时0分0秒的毫秒数,与Java中的currentTimeMilis()函数一样. 例子: public function getCurrentMilis() { $mill_time = microtime(); $timeInfo = explode(' ', $mill_time); $milis_time = sprintf('%d%03d',$timeInfo[

  • 微信小程序 火车票查询实例讲解

    微信小程序 简单实例---火车票查询应用,学习掌握小程序框架,及开发步骤的实现.微信小程序体现了轻便,易用的特点,并且上手快,前端知识好学易用. 1. 相关链接 本本项目代码获取地址 Github:https://github.com/VincentWYJ/WXAppTrain.git: Blog file:http://files.cnblogs.com/files/tgyf/WXAppTrain.rar: 微信小程序开发学习资料 微信开发者平台:https://mp.weixin.qq.co

  • jQuery往返城市和日期查询实例讲解

    大多旅游网站上都提供了一个城市和日期输入查询的功能.用户在输入框中只需输入城市的拼音或者简称就可以即时查询到相关城市的名称,选择日期时则是出现两个月的日历控件,只需点选日期即可,整个操作简捷明了. 本文用到了jquery ui库的datepicker插件来控制日历以及输入城市提示的插件. XHTML <div class="qline"> <label for="arrcity">出发城市:</label><input ty

  • MySQL通过实例化对象参数查询实例讲解

    本篇文章给大家带来的内容是关于MySQL如何通过实例化对象参数查询数据 ?(源代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助. public static string QueryByEntity<T>(T t) where T : new() { string resultstr = string.Empty; MySqlDataReader reader = null; try { Type type = typeof(T); PropertyInfo[] prope

  • mysql多表连接查询实例讲解

    实际的项目,存在多张表的关联关系.不可能在一张表里面就能检索出所有数据.如果没有表连接的话,那么我们就需要非常多的操作.比如需要从A表找出限制性的条件来从B表中检索数据.不但需要分多表来操作,而且效率也不高.比如书中的例子: 代码如下: SELECT FId FROM T_Customer WHERE FName='MIKE' 这个SQL语句返回2,也就是姓名为MIKE 的客户的FId值为2,这样就可以到T_Order中检索FCustomerId等于2 的记录: 代码如下: SELECT FNu

  • C# 获取当前总毫秒数的实例讲解

    在.Net下DateTime.Ticks获得的是个long型的时间整数,具体表示是至0001 年 1 月 1 日午夜 12:00:00 以来所经过时间以100纳秒的数字.转换为秒为Ticks/10000000,转换为毫秒Ticks/10000. 如果要获取从1970年1月1日至当前时间所经过的毫秒数,代码如下: //获取当前Ticks long currentTicks= DateTime .Now.Ticks; DateTime dtFrom = new DateTime (1970, 1,

  • Android Camera实现毫秒级拍照实例

    我们知道自定义Camera需要以下几步 打开相机,即实例化Camera对象,Camera camera = Camera.open(); 设置Camera的相关参数,Camera.Parameters parameters = camera.getParameters(); 打开预览,camera.setPreviewDisplay(surfaceholder); camera.startPreview(); 获取图片,这里只是从预览中获取因此使用,camera.setPreviewCallb

  • 实例讲解多个js毫秒倒计时同时进行效果

    本文实例讲解js毫秒倒计时同时进行效果的代码,分享给大家供大家参考,具体内容如下 效果图: 实现功能:调用一个函数,传入html元素的id,和一个截止时间(unix时间戳),在该html元素中打印出到当前到截止时间为止的倒计时,精确到毫秒: 效果图如下: <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <meta name="viewport" conte

  • Java分页查询--分页显示(实例讲解)

    当数据库中数据条数过多时,一个页面就不能显示,这是要设置分页查询,首先要使用的是数据库sql语句的limit条件实现分组查询 sql语句大概形式为: select * from table limit 开始索引,显示条数 用该语句就会实现分块查询,并且每页显示固定条数. 首先要实现后台分页,我们需要知道它有多少页,每页有多少行,这就需要知道一共多少行,调用sql语句时还需要知道每一页的开始索引,开始索引是根据当前页数算出来的,所以还需要知道当前页数,查询后会返回一个列表存储当前页数据.将这些属性

随机推荐