使用bitset实现毫秒级查询（二）

发表于 | 分类于
字数统计: 1.4k | 阅读时长 ≈ 7

在上一篇中我们了解了bitset索引的基本用法，本篇开始学习bitset索引更新及一些复杂查询。

1.bitset索引更新

  因为我们的数据是在系统启动时全部加载进内存，所以当数据库数据发生变化时要实时通知到内存，可以使用消息队列的方式实现：将新增或者修改的数据写入kafka,然后在索引服务中从kafka中读出数据更新索引.
在UserIndexStore类中增加更新索引方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
	 * 更新索引
	 * @param user
	 */
	public void updateIndex(User user) {
		String name = user.getName();
		Integer userIndex = this.nameIndexMap.get(name);
		if (userIndex != null) {
			clear(userIndex);//清除bitset对应位置的值
			update(user, userIndex);
			this.userMap.put(userIndex, user);
			this.nameIndexMap.put(user.getName(), userIndex);
		} else {
			//新增时会有并发问题
			synchronized (this) {
				int index = this.userMap.size() + 1;
				createIndex(user, index);
			}
		}

	}

	private void update(User user, Integer userIndex) {
		getAddress().update(user.getAddress(), userIndex);
		getAge().update(user.getAge(), userIndex);
		getGender().update(user.getGender(), userIndex);

	}

	private void clear(Integer index) {
		getAddress().clear(index);
		getAge().clear(index);
		getGender().clear(index);
	}

在BitSetIndexModel类中增加clear()方法

1
2
3
4
5
6
7
8
9
10
11
   /**
 * 对第i位置0
 * @param i
 */
public void clear(Integer i) {
	for (BitSet bs : bsList) {
		if (bs != null && i < bs.length()) {
			bs.clear(i);
		}
	}
}
2.bitset进阶查询

‘>=’，’<=’，between and
在BitSetIndexModel类中增加如下方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public List<String> getHigherList(String str) {
		List<String> newlist = new ArrayList<String>();
		newlist.add(str);
		newlist.addAll(list);
		// 排序
		Collections.sort(newlist);
		// 查找str在list中的位置
		int fromIndex = Collections.binarySearch(newlist, str);
		if (fromIndex >= 0) {
			// 如果map中不包含当前值则 index后移一位
			if (map.get(str) == null) {
				fromIndex++;
			}
			return newlist.subList(fromIndex, newlist.size());
		} else {
			return new ArrayList<String>();
		}
	}

	public List<String> getLowerList(String str) {
		List<String> newlist = new ArrayList<String>();
		newlist.add(str);
		newlist.addAll(list);
		// 排序
		Collections.sort(newlist);
		// 查找str在list中的位置
		int endIndex = Collections.binarySearch(newlist, str);
		if (endIndex >= 0) {
			return newlist.subList(0, endIndex + 1);
		} else {
			return new ArrayList<String>();
		}
	}

	@SuppressWarnings("unchecked")
	public <T extends Comparable<? super T>> List<T> getRange(T min, T max, Comparator<? super T> c) {
		List<T> newlist = new ArrayList<T>();
		for (String s : list) {
			newlist.add((T) (s));
		}
		Collections.sort(newlist);
		// 查找str在list中的位置
		int fromIndex = minBinarySearch(newlist, min, c);
		int endIndex = maxBinarySearch(newlist, max, c);
		if (fromIndex >= 0 && endIndex <= list.size() - 1) {
			if (fromIndex == endIndex) {
				return newlist.subList(fromIndex, endIndex + 1);
			}
			return newlist.subList(fromIndex, ++endIndex);
		} else {
			return new ArrayList<T>();
		}
	}

	/**
	 *
	 * @param list
	 * @param key
	 * @return
	 */
	private static <T> int maxBinarySearch(List<T> list, T key, Comparator<? super T> c) {
		int low = 0;
		int high = list.size() - 1;
		int mid = 0;
		while (low <= high) {
			mid = (low + high) >>> 1;
			T midVal = list.get(mid);
			int cmp = c.compare(midVal, key);
			if (cmp < 0) {
				low = mid + 1;
			} else if (cmp > 0) {
				high = mid - 1;
			} else {
				return mid; // key found
			}
		}
		if (mid == low) {
			return high;
		} else {
			return mid;
		}
	}

	private static <T> int minBinarySearch(List<T> list, T key, Comparator<? super T> c) {
		int low = 0;
		int high = list.size() - 1;
		int mid = 0;
		while (low <= high) {
			mid = (low + high) >>> 1;
			T midVal = list.get(mid);
			int cmp = c.compare(midVal, key);
			if (cmp < 0) {
				low = mid + 1;
			} else if (cmp > 0) {
				high = mid - 1;
			} else {
				return mid; // key found
			}
		}
		if (high == mid) {
			return low;
		} else {
			return mid;
		}
	}

在UserIndexStore中增加以下方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
	 * 查询年龄大于等于指定值的user索引
	 * @param age
	 * @return
	 */
	public BitSet findUserByAgeHigher(String age) {
		BitSetIndexModel indexModel = getAge();
		List<String> strs = indexModel.getHigherList(age);
		BitSet bitset = null;
		for (String str : strs) {
			bitset = indexModel.or(str, bitset);
		}
		return bitset;
	}

	/**
	 * 查询age小于等于指定值的user索引
	 * @param age
	 * @return
	 */
	public BitSet findUserByAgeLower(String age) {
		BitSetIndexModel indexModel = getAge();
		List<String> strs = indexModel.getLowerList(age);
		BitSet bitset = null;
		for (String str : strs) {
			bitset = indexModel.or(str, bitset);
		}
		return bitset;
	}

	/**
	 * 查询age在某两个值区间内的user索引
	 * @param min
	 * @param max
	 * @return
	 */
	public BitSet findUserByAgeBetweenAnd(String min, String max) {
		BitSetIndexModel indexModel = getAge();
		List<String> strs = indexModel.getRange(min, max, new Comparator<Object>() {
			@Override
			public int compare(Object o1, Object o2) {

				return Integer.valueOf(o1 == null ? "0" : o1.toString()).compareTo(Integer.valueOf(o2 == null ? "0" : o2.toString()));
			}
		});
		BitSet bitset = null;
		for (String str : strs) {
			bitset = indexModel.or(str, bitset);
		}
		return bitset;
	}
测试，查询年龄在16-17之间的北京女孩。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class BitSetTestRange {

	public static void main(String[] args) {
		List<User> users = buildData();
		UserIndexStore.getInstance().createIndex(users);
		ExecutorService executorService = Executors.newFixedThreadPool(50);
		int num = 2000;
		long begin1 = System.currentTimeMillis();
		for (int i = 0; i < num; i++) {
			Runnable syncRunnable = new Runnable() {
				@Override
				public void run() {
					BitSet bs = UserIndexStore.getInstance().query("北京", "girl", null);
					BitSet ageBs = UserIndexStore.getInstance().findUserByAgeBetweenAnd("16", "17");
					bs.and(ageBs);
					for (Integer index : BitSetIndexModel.getRealIndexs(bs)) {
						UserIndexStore.getInstance().findUser(index);
					}
				}
			};
			executorService.execute(syncRunnable);
		}
		executorService.shutdown();
		while (true) {
			try {
				if (executorService.awaitTermination(1, TimeUnit.SECONDS)) {
					System.err.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 < 1000000; 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;
	}

}
1
单次查询时间为：22ms

相比”=”查询，区间查询速度慢了一些，但还在预期之内。

总结

  以上就实现了一个bitset索引，支持索引创建，更新，查询。并且因为没有传统的网络传输和磁盘io,所以速度非常快，基本上响应时间都在10ms以内。如果需要我可以在下一篇使用spring cloud搭建一个较完整的demo，供大家参考使用。