BTreeMap 为 MapDB 提供了 TreeMap 和 TreeSet。它基于无锁并发 B-链树（B-Linked-Tree）。对于小键，它具有出色的性能，并且具有良好的垂直可扩展性。
BTreeMap 具有可选参数，这些参数可以通过使用构建器来指定：
其中最重要的是序列化器。通用序列化存在一些猜测和开销，因此如果使用更具体的序列化器，总能获得更好的性能。要指定键和值的序列化器，请使用下面的代码。在 Serializer 接口的静态字段上有数十个现成可用的序列化器：
// 创建 BTreeMap 实例
public static class CreateBTreeMapExample {
public static void main(String[] args) {
try(DB db = DBMaker.memoryDB().make()) {
BTreeMap<Long, String> map = db.treeMap("map")
// 指定键序列化器
.keySerializer(Serializer.LONG)
// 指定值序列化器
.valueSerializer(Serializer.STRING)
.createOrOpen();
map.put(100L, "Hello BTreeMap");
System.out.println(map.get(100L));
}
}
}另一个有用的参数是大小计数器。默认情况下，BTreeMap 不会跟踪其大小，调用 map.size() 需要进行线性扫描来计数所有条目。如果启用了大小计数器，在这种情况下，map.size() 会立即执行，但插入操作会有一些开销。
BTrees 将其所有键和值存储为 btree 节点的一部分。节点大小对性能影响很大。大节点意味着许多键必须在查找时反序列化。较小的节点加载速度更快，但会使大型 BTrees 更深，需要更多操作。默认最大节点大小为 32个 条目，可以通过以下方式更改：
// 启用大小计数器
public static class BTreeMapCounterExample {
public static void main(String[] args) {
try(DB db = DBMaker.memoryDB().make()) {
BTreeMap<Long, String> map = db.treeMap("map")
.keySerializer(Serializer.LONG)
.valueSerializer(Serializer.STRING)
.counterEnable() // 启用大小计数器
.createOrOpen();
map.put(100L, "Hello BTreeMap");
System.out.println(map.size());
}
}
}值也作为 BTree 叶节点的一部分进行存储。较大的值意味着巨大的开销，在单次 map.get("key") 操作中，会有 32 个值被反序列化，但只返回一个值。在这种情况下，最好将值存储在叶节点外部，即单独的记录中。此时，叶节点仅包含一个 6 字节的 recid（记录ID），用于指向该值。
较大的值也可以被压缩以节省空间。此示例将值存储在 BTree 叶节点外部，并对每个值应用压缩：
// 将值存储在叶子节点之外
public static class BTreeMapValuesOutsideNodesExample {
public static void main(String[] args) {
try(DB db = DBMaker.memoryDB().make()) {
BTreeMap<Long, String> map = db.treeMap("map")
.keySerializer(Serializer.LONG)
.valueSerializer(Serializer.STRING)
.valuesOutsideNodesEnable() // 将值存储在叶子节点之外
.createOrOpen();
map.put(100L, "Hello BTreeMap");
System.out.println(map.get(100L));
}
}
}BTreeMap 需要以某种方式对其键进行排序。默认情况下，它依赖于大多数 Java 类实现的 Comparable 接口。如果未实现该接口，则必须提供一个键序列化器。例如，可以对对象数组进行比较：
BTreeMap<Object[], Long> map = db.treeMap("map")
// 对未知对象使用数组序列化器
.keySerializer(new SerializerArray())
// 或者为特定对象（如String）使用包装的序列化器
.keySerializer(new SerializerArray(Serializer.STRING))
.createOrOpen();此外，基本类型数组也可以用作键。可以用 byte[] 替换 String，这会直接带来更好的性能：
BTreeMap<byte[], Long> map = db.treeMap("map")
.keySerializer(Serializer.BYTE_ARRAY)
.valueSerializer(Serializer.LONG)
.createOrOpen();BTreeMap 的性能得益于其处理键的方式。让我们用长整型（Long）键的例子来对此进行说明。
一个长整型键在序列化后占用 8 个字节。为了最大限度地减少空间使用，可以对这个值进行压缩以使其更小。例如，数字 10 将占用 1 个字节，300 将占用 2 个字节，10000 将占用 3 个字节，依此类推。为了让键更易于压缩，我们需要将它们存储为更小的值。由于键是排序的，所以我们可以使用增量压缩。这种方式会完整存储第一个值，然后只存储连续数字之间的差值。
另一项改进是加快反序列化速度。在普通的 TreeMap 中，键是以包装形式存储的，例如 Long[]。这会带来巨大的开销，因为每个键都需要一个新的指针、类头…… BTreeMap 会将键存储在基本类型数组 long[]中。最后，如果键足够小，甚至可以存储在 int[] 中。而且由于数组具有更好的内存局部性，二分查找的性能会有极大提升。
对数字进行这种优化很简单。但是 BTreeMap 也适用于其他键，例如 String（通用前缀压缩、带偏移量的单字节[]）、byte[]、UUID、Date 等。
这种优化会自动应用。您只需提供专门的键序列化器即可：
BTreeMap<byte[], Long> map = db.treeMap("map")
.keySerializer(Serializer.LONG) // 看这里
.valueSerializer(Serializer.LONG)
.createOrOpen();有几个选项和实现来打包键。有关详细信息，请查看 Serializer 类中带有 _PACK 后缀的静态字段。
无锁设计的一个权衡是删除后的碎片化问题。 B-链树（B-Linked-Tree）在条目移除后，一旦 B 树节点变为空，也不会将其删除。如果您填满一个 BTreeMap 然后删除所有条目，大约 40% 的空间不会被释放。任何值的更新（键被保留）都不会受这种碎片化的影响。
这种碎片化不同于存储碎片化，因此 DB.compact() 不会起作用。一种解决方案是将所有内容迁移到一个新的 BTreeMap中。由于借助数据泵流处理速度很快，新的映射将不存在碎片化问题，并且节点局部性更好（理论上对磁盘缓存更友好）。
未来，我们将提供 BTreeMap 包装器，它会自动执行这种压缩操作。该包装器将使用三个集合：
第一个 BTreeMap 是只读的，并且也会包含数据。
第二个小型映射将包含更新内容。
第三个映射会定期通过合并前两个映射生成，并会与主映射进行交换。Cassandra 和其他数据库中的 SSTable 的工作方式与此类似。
对于基于数组的键（元组、字符串或数组），MapDB 提供前缀子映射。它使用区间，因此前缀子映射是延迟加载的，不会加载所有键。下面是一个在 byte[] 键上使用前缀的示例：
// 前缀子映射示例
public static class BTreeMapPrefixSubMapExample {
public static void main(String[] args) {
try(DB db = DBMaker.memoryDB().make()) {
BTreeMap<byte[], Integer> map = db
.treeMap("towns", Serializer.BYTE_ARRAY, Serializer.INTEGER)
.createOrOpen();
map.put("New York".getBytes(), 1);
map.put("New Jersey".getBytes(), 2);
map.put("Boston".getBytes(), 3);
// 获取所有以 New* 开头的城市
Map<byte[], Integer> newCities = map.prefixSubMap("New".getBytes());
newCities.forEach((k,v) -> {
System.out.println(new String(k, StandardCharsets.UTF_8) + "=" + v);
});
}
}
}MapDB 支持以 Object[] 形式存在的复合键。区间子映射可用于获取元组子组件，或者创建一种简单形式的多映射。对象数组不具有可比性，因此你需要使用提供比较器的专用序列化器。
以下是一个以 Object[] 形式创建 Map<Tuple3<String, String, Integer>, Double> 的示例。第一个组件是城镇，第二个是街道，第三个是门牌号。它还有更多内容，源代码在 github 上。要序列化和比较元组，请使用 SerializerArrayTuple，它将每个元组组件的序列化器作为构造函数参数：
// 初始化数据库和映射
DB db = DBMaker.memoryDB().make();
BTreeMap<Object[], Integer> map = db.treeMap("towns")
.keySerializer(new SerializerArrayTuple(
Serializer.STRING, Serializer.STRING, Serializer.INTEGER))
.valueSerializer(Serializer.INTEGER)
.createOrOpen();一旦 map 被填充，我们可以通过使用前缀 submap（town 是元组中的第一个组件）获得 Cong 镇的所有房屋：
// 获取 Cong 镇的所有房屋（镇是元组中的主要组成部分）
Map<Object[], Integer> cong =
map.prefixSubMap(new Object[]{"Cong"});前缀子映射等同于使用 submap 方法的范围查询：
区间子映射只能过滤左侧的组件。要获取中间的组件，我们必须将子映射与 for 循环结合使用：
cong = map.subMap(
new Object[]{"Cong"}, //较短的数组是“负无穷大”
new Object[]{"Cong",null,null} // null 是正无穷大
);子映射是可修改的，因此我们可以通过调用子映射的 clear() 等方法来删除一个城镇内的所有房屋。
完整示例：
// 复合键和元组示例
public static class BTreeMapArrayTupleExample {
public static void main(String[] args) {
// 初始化 db 和 map
try(DB db = DBMaker.memoryDB().make()) {
BTreeMap<Object[], Integer> map = db.treeMap("towns")
// 设置key序列化器为 SerializerArrayTuple
.keySerializer(new SerializerArrayTuple(
Serializer.STRING, Serializer.STRING, Serializer.INTEGER))
.valueSerializer(Serializer.INTEGER)
.createOrOpen();
//初始化值
String[] towns = {"Galway", "Ennis", "Gort", "Cong", "Tuam"};
String[] streets = {"Main Street", "Shop Street", "Second Street", "Silver Strands"};
int[] houseNums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (String town : towns) {
for (String street : streets) {
for (int house : houseNums) {
int income = 30000;
map.put(new Object[]{town, street, house}, income);
}
}
}
// 获取 Cong 的所有房屋（城镇是元组中的主要组成部分）
Map<Object[], Integer> cong =
map.prefixSubMap(new Object[]{"Cong"});
System.out.println("实际房屋数量：" + (houseNums.length * streets.length) +
", 查询的房屋数量：" + cong.size());
cong = map.subMap(
new Object[]{"Cong"}, //较短的数组是“负无穷大”
new Object[]{"Cong", null, null} //null 是正无穷大
);
System.out.println("实际房屋数量：" + (houseNums.length * streets.length) +
", 查询的房屋数量：" + cong.size());
int total = 0;
for (String town : towns) { //第一个循环遍历各个城镇
for (Integer salary : //第二个循环遍历主街上的所有房屋
map.prefixSubMap(new Object[]{town, "Main Street"}).values()) {
total += salary; //并计算总和
}
}
System.out.println("所有主街的工资总和为：" + total);
System.out.println("实际工资=" + (30000 * towns.length * houseNums.length) + ", 查询工资=" + total);
}
}
}Multimap 是一种映射（Map），它将多个值与单个键相关联。在 Guava 或 Eclipse Collections 中可以找到相关示例。它可以写成 Map<Key,List<Value>> 的形式，但在 MapDB 中这样做效果并不好，因为我们需要键和值是不可变的，而列表（List）并不是不可变的。
有一个计划是在 MapDB 中直接实现来自 Guava 和 Eclipse Collections 的 Multimap。但在那之前，有一种选择是将 SortedSet 与元组和区间子集结合使用。下面是一个示例，它构建了集合，插入了一些数据，并获取了与键（元组的第一个组件）相关联的所有值（元组的第二个组件）：
// Multimap 示例
public static class BTreeMapMultimapExample {
public static void main(String[] args) {
try(DB db = DBMaker.memoryDB().make()) {
// 初始化多重映射：Map<String,List<Integer>>
NavigableSet<Object[]> multimap = db.treeSet("towns")
//设置元组序列化器
.serializer(new SerializerArrayTuple(Serializer.STRING, Serializer.INTEGER))
.counterEnable()
.counterEnable()
.counterEnable()
.createOrOpen();
// 填充数据，键是元组（数组）中的第一个组件，值是第二个组件
multimap.add(new Object[]{"John",1});
multimap.add(new Object[]{"John",2});
multimap.add(new Object[]{"Anna",1});
// 打印所有与约翰相关联的值：
Set johnSubset = multimap.subSet(
new Object[]{"John"}, // 区间下限
new Object[]{"John", null}); // 区间上限，null 表示正无穷大
johnSubset.forEach(e -> {
Object[] val = (Object[]) e;
System.out.println(Arrays.toString(val));
});
}
}
}BTreeMap 更适合较小的键，例如数字和短字符串。
更多关于 MapDB 的知识，请继续学习后续教程🚀
川公网安备51010802032098