从零构建分布式索引系统 OriginDB：原型

作者：null

2025-07-05
山东
本文字数：3488 字
阅读完需：约 11 分钟

序

什么是 OriginDB

OriginDB 是一款全内存分布式索引系统，用于支持数据复杂的检索需求。

为什么想做 OriginDB

本科毕业，毕设方向《搜索引擎的设计与实现》，算是索引检索初探。
15 年~24 年间，从事广告系统开发，主攻广告检索和在线投放。在某知名大厂自主完成分布式内存索引系统 Kunl。
25 年离职，闲来无事，总结了下内存索引的新想法，随计划开发 OriginDB，一款分布式内存索引系统 O 中文名“起源”，纪念开发生涯。

OriginDB 有什么特点

易使用：类关系型数据库设计，支持 sql 查询，对开发人员友好，使用门槛低。
高性能：不需考虑 IO，充分发挥内存优势，充分使用多种内存友好的数据结构。
分布式：实现节点发现，数据同步，最终一致性，开放服务，可独立部署，用于生产环境。

关于本文

初步构建一个索引系统原型，阐述 OriginDB 内核的思路，后续会在该原型上演进出完整的系统

理论

什么是索引

加速查询的数据结构，本质空间换时间，但增加写入维护成本

索引常用数据结构

注：还有些高级数据结构如：字符串前后缀查询：“FST”，“双向 Radix 树”，地理位置查询：“KDTree”，“Geohash 网格索引” 后续随演进介绍。

快速原型构建：模拟 mysql 索引内存版

理论：Innodb 索引

主键索引：B+Tree 索引主键到数据
二级索引：B+Tree 索引字段值到主键，回表获取数据

需求

表

CREATE TABLE `user`(    `id`   INT PRIMARY KEY COMMENT 'id',    `age`  TINYINT COMMENT '年龄',    `city` VARCHAR(50) COMMENT '城市') COMMENT='用户表';

复制代码

数据

INSERT INTO user (id, age, city)VALUES (1, 10, 'beijing'),  -- 10岁，北京       (2, 20, 'shanghai'), -- 20岁，上海       (3, 30, 'beijing'),  -- 30岁，北京       (4, 40, 'shanghai'); -- 40岁，上海

复制代码

查询

-- 主键查询SELECT id, age, cityFROM userWHERE id = 1;
-- 复合查询SELECT id, age, cityFROM userWHERE age BETWEEN 20 AND 30  AND address = 'beijing';

复制代码

设计

前提：全内存，不需要考虑 IO
1）因此二级索引可以使用对象引用，不需要回表，提高效率（此设计并不好，后续演进）
2）二级索引到单字段索，可支持查询任意组合任意使用，提高灵活性

数据结构：
主键索引：Map<Object, T> mainIndex；其中 key 是主键
二级索引集合：Map<String, Map<Object, Set<T>> secondaryIndex；其中 key 是字段名，子 key 是字段值，value 是 id 列表
检索过程：
获取每个字段过滤结果，集合结果集获得最终结果

实现

数据库表

public class Table<T extends Supplier<Integer>> {
    /**     * 主键索引     */    private final Map<Integer, T> mainIndex = new HashMap<>();
    /**     * 二级索引：key 字段名，subkey 字段值，value：符合的对象列表     */    private final Map<String, Map<Object, Set<T>>> secondaryIndex = new HashMap<>();
    @SneakyThrows    public final void insert(T... objs) {        for (T obj : objs) {            // 插入数据            mainIndex.put(obj.get(), obj);
            Field[] fields = obj.getClass().getDeclaredFields();            for (Field field : fields) {                field.setAccessible(true);
                Object fieldValue = field.get(obj);                // 插入二级索引                secondaryIndex                        .computeIfAbsent(field.getName(),                                fieldName -> {                                    if (fieldValue instanceof Comparable) {                                        return new TreeMap<>();                                    } else {                                        return new HashMap<>();                                    }                                })                        .computeIfAbsent(fieldValue, fieldName -> new HashSet<>())                        .add(obj);            }        }
    }
    // 查询 ===============================
    public T getById(Integer id) {        return mainIndex.get(id);    }
    public Collection<T> search(String indexName, Object value) {        Map<Object, Set<T>> values = secondaryIndex.get(indexName);
        if (MapUtils.isEmpty(values)) {            return Collections.emptySet();        }
        return secondaryIndex.get(indexName).get(value);    }
    public Collection<T> rangeSearch(String indexName, Object from, boolean fromInclusive, Object to, boolean toInclusive) {        Map<Object, Set<T>> values = secondaryIndex.get(indexName);        if (!(values instanceof NavigableMap)) {            throw new UnsupportedOperationException("unsupported range search!");        }        if (MapUtils.isEmpty(values)) {            return Collections.emptySet();        }        Collection<Set<T>> result = ((NavigableMap<Object, Set<T>>) values)                .subMap(from, fromInclusive, to, toInclusive).values();
        return or(result);    }
    // 工具方法 =============================    public static <T> Collection<T> or(Collection<Set<T>> results) {        if (CollectionUtils.isEmpty(results)) {            return Collections.emptySet();        }
        if (results.size() == 1) {            return results.iterator().next();        }
        Collection<T> finalResult = new HashSet<>();        for (Set<T> resultItem : results) {            finalResult = CollectionUtils.union(finalResult, resultItem);        }        return finalResult;    }}

复制代码

使用

 public static void main(String[] args) {        // 测试类        @ToString        @AllArgsConstructor        class User implements Supplier<Integer> {            private Integer id;            private Integer age;            private String address;
            @Override            public Integer get() {                return id;            }        }
        // 1.建表        Table<User> table = new Table<>();
        // 2.插入数据 并建立索引 =========================
        table.insert(                // age = 10， salary = 10                new User(1, 10, "beijing"),                // age = 20， salary = 100                new User(2, 20, "shanghai"),                // age = 10， salary = 100                new User(3, 30, "beijing"),                // age = 20， salary = 1000                new User(4, 40, "shanghai")        );

        //3 查询        // 主键        System.out.println("SQL：where id = 1 ：");        System.out.println(table.getById(1));        System.out.println("======================================");
        // 多字段查询        System.out.println("SQL: where (age BETWEEN 20 AND 30) AND address = 'beijing': ");        Collection<User> ageAddressResult = CollectionUtils.intersection(                table.rangeSearch("age", 20, true, 30, true),                table.search("address", "beijing"));
        ageAddressResult.forEach(System.out::println);        System.out.println("======================================");    }

复制代码

结果

SQL：where id = 1 ：User(id=1, age=10, address=beijing)======================================SQL: where (age BETWEEN 20 AND 30) AND address = 'beijing': User(id=3, age=30, address=beijing)======================================

复制代码

总结

演进规划

索引

抽象库，表，正排，倒排等数据结构。
倒排存储逻辑 id：对象引用，更新删除，影响 JavaGC 回收，最好使用数值类型的 ID 方便空间优化。
软删除、数据清理：实时清理词典倒排成本高
存活对象列表：查询后过滤软删除的无效数据

查询

查询条件：=，!= ，<>，>，>=， <， <= ， IN ，NOT IN, BETWEEN AND
查询关系：AND ，OR ，NOT
查询组：()

未完待续

附录

纪念 n 年前的文章：《基于BitSet的广告索引检索引擎实现》

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/6abb3e4542a5f9e36492df6bf】。未经作者许可，禁止转载。

null

关注

还未添加个人签名 2015-05-11 加入

还未添加个人简介

发布

暂无评论

创作场景

从零构建分布式索引系统 OriginDB：原型

序

什么是 OriginDB

为什么想做 OriginDB

OriginDB 有什么特点

关于本文

理论

什么是索引

索引常用数据结构

快速原型构建：模拟 mysql 索引内存版

理论：Innodb 索引

需求

表

数据

查询

设计

实现

数据库表

使用

结果

总结

演进规划

索引

查询

未完待续

附录

null

评论