算法详解：索引原理 - 数据库查询加速的核心技术

1
2
3
4
5

A[数据表 Table] → B[索引结构 Index]
B → C[B+树索引]
B → D[哈希索引]
B → E[位图索引]
B → F[全文索引]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

📚 图书馆查找书籍:
无索引: 逐个书架翻找，从A区找到Z区
有索引: 查看索引卡片，直接定位到具体书架位置

🏢 电话簿查找联系人:
无索引: 从第一页翻到最后一页寻找姓名
有索引: 按首字母分类，快速定位到相关页面

🔍 搜索引擎工作原理:
Google: 建立网页倒排索引，根据关键词快速定位相关页面
百度: 预先处理网页内容，建立词汇到页面的映射关系

1
2
3
4
5

A[根节点: 50, 100] → B[内部节点: 25, 40]
A → C[内部节点: 75, 90]
A → D[内部节点: 125, 150]
B → E[叶子: 10,15,20]
B → F[叶子: 25,30,35]

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

/**
 * B+树索引实现
 */
public class BPlusTreeIndex<K extends Comparable<K>, V> {
    private static final int DEFAULT_ORDER = 4; // B+树的阶数

    private Node<K, V> root;
    private int order;

    public BPlusTreeIndex() {
        this(DEFAULT_ORDER);
    }

    public BPlusTreeIndex(int order) {
        this.order = order;
        this.root = new LeafNode<>();
    }

    /**
     * 抽象节点类
     */
    abstract static class Node<K extends Comparable<K>, V> {
        List<K> keys;
        boolean isLeaf;

        Node(boolean isLeaf) {
            this.keys = new ArrayList<>();
            this.isLeaf = isLeaf;
        }

        abstract boolean isFull(int order);
        abstract Node<K, V> split(int order);
        abstract K getFirstKey();
    }

    /**
     * 内部节点实现
     */
    static class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<Node<K, V>> children;

        InternalNode() {
            super(false);
            this.children = new ArrayList<>();
        }

        @Override
        boolean isFull(int order) {
            return keys.size() >= order - 1;
        }

        @Override
        Node<K, V> split(int order) {
            int mid = keys.size() / 2;

            InternalNode<K, V> newNode = new InternalNode<>();
            newNode.keys.addAll(keys.subList(mid + 1, keys.size()));
            newNode.children.addAll(children.subList(mid + 1, children.size()));

            keys.subList(mid, keys.size()).clear();
            children.subList(mid + 1, children.size()).clear();

            return newNode;
        }

        @Override
        K getFirstKey() {
            return keys.isEmpty() ? null : keys.get(0);
        }

        /**
         * 插入子节点
         */
        void insertChild(K key, Node<K, V> child) {
            int pos = Collections.binarySearch(keys, key);
            if (pos < 0) {
                pos = -pos - 1;
            }

            keys.add(pos, key);
            children.add(pos + 1, child);
        }
    }

    /**
     * 叶子节点实现
     */
    static class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<V> values;
        LeafNode<K, V> next; // 叶子节点链表，支持范围查询

        LeafNode() {
            super(true);
            this.values = new ArrayList<>();
        }

        @Override
        boolean isFull(int order) {
            return keys.size() >= order;
        }

        @Override
        Node<K, V> split(int order) {
            int mid = keys.size() / 2;

            LeafNode<K, V> newNode = new LeafNode<>();
            newNode.keys.addAll(keys.subList(mid, keys.size()));
            newNode.values.addAll(values.subList(mid, values.size()));

            // 更新链表指针
            newNode.next = this.next;
            this.next = newNode;

            keys.subList(mid, keys.size()).clear();
            values.subList(mid, values.size()).clear();

            return newNode;
        }

        @Override
        K getFirstKey() {
            return keys.isEmpty() ? null : keys.get(0);
        }

        /**
         * 插入键值对
         */
        void insert(K key, V value) {
            int pos = Collections.binarySearch(keys, key);
            if (pos >= 0) {
                // 键已存在，更新值
                values.set(pos, value);
            } else {
                // 插入新键值对
                pos = -pos - 1;
                keys.add(pos, key);
                values.add(pos, value);
            }
        }

        /**
         * 查找值
         */
        V find(K key) {
            int pos = Collections.binarySearch(keys, key);
            return pos >= 0 ? values.get(pos) : null;
        }
    }

    /**
     * 插入操作
     */
    public void insert(K key, V value) {
        InsertResult<K, V> result = insertInternal(root, key, value);

        if (result.newChild != null) {
            // 根节点分裂，创建新根
            InternalNode<K, V> newRoot = new InternalNode<>();
            newRoot.keys.add(result.promotedKey);
            newRoot.children.add(root);
            newRoot.children.add(result.newChild);
            root = newRoot;
        }
    }

    private InsertResult<K, V> insertInternal(Node<K, V> node, K key, V value) {
        if (node.isLeaf) {
            LeafNode<K, V> leaf = (LeafNode<K, V>) node;
            leaf.insert(key, value);

            if (leaf.isFull(order)) {
                Node<K, V> newLeaf = leaf.split(order);
                return new InsertResult<>(newLeaf.getFirstKey(), newLeaf);
            }

            return new InsertResult<>(null, null);
        } else {
            InternalNode<K, V> internal = (InternalNode<K, V>) node;
            int childIndex = findChildIndex(internal, key);

            InsertResult<K, V> result = insertInternal(
                internal.children.get(childIndex), key, value);

            if (result.newChild != null) {
                internal.insertChild(result.promotedKey, result.newChild);

                if (internal.isFull(order)) {
                    Node<K, V> newInternal = internal.split(order);
                    K promotedKey = internal.keys.remove(internal.keys.size() - 1);
                    return new InsertResult<>(promotedKey, newInternal);
                }
            }

            return new InsertResult<>(null, null);
        }
    }

    private int findChildIndex(InternalNode<K, V> node, K key) {
        int pos = Collections.binarySearch(node.keys, key);
        return pos >= 0 ? pos + 1 : -pos - 1;
    }

    /**
     * 查找操作
     */
    public V search(K key) {
        return searchInternal(root, key);
    }

    private V searchInternal(Node<K, V> node, K key) {
        if (node.isLeaf) {
            LeafNode<K, V> leaf = (LeafNode<K, V>) node;
            return leaf.find(key);
        } else {
            InternalNode<K, V> internal = (InternalNode<K, V>) node;
            int childIndex = findChildIndex(internal, key);
            return searchInternal(internal.children.get(childIndex), key);
        }
    }

    /**
     * 范围查询 - B+树的优势
     */
    public List<V> rangeQuery(K startKey, K endKey) {
        List<V> results = new ArrayList<>();
        LeafNode<K, V> current = findLeafNode(startKey);

        while (current != null) {
            for (int i = 0; i < current.keys.size(); i++) {
                K key = current.keys.get(i);
                if (key.compareTo(startKey) >= 0 && key.compareTo(endKey) <= 0) {
                    results.add(current.values.get(i));
                } else if (key.compareTo(endKey) > 0) {
                    return results;
                }
            }
            current = current.next;
        }

        return results;
    }

    private LeafNode<K, V> findLeafNode(K key) {
        Node<K, V> current = root;

        while (!current.isLeaf) {
            InternalNode<K, V> internal = (InternalNode<K, V>) current;
            int childIndex = findChildIndex(internal, key);
            current = internal.children.get(childIndex);
        }

        return (LeafNode<K, V>) current;
    }

    /**
     * 插入结果辅助类
     */
    static class InsertResult<K, V> {
        final K promotedKey;
        final Node<K, V> newChild;

        InsertResult(K promotedKey, Node<K, V> newChild) {
            this.promotedKey = promotedKey;
            this.newChild = newChild;
        }
    }
}

 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

/**
 * B+树性能分析工具
 */
public class BPlusTreePerformanceAnalyzer {

    /**
     * 计算B+树的高度
     */
    public static int calculateHeight(int totalRecords, int order) {
        // 叶子节点平均存储 order/2 个记录
        int leafCapacity = order / 2;
        int leafNodes = (int) Math.ceil((double) totalRecords / leafCapacity);

        // 内部节点平均有 order/2 个子节点
        int internalFanout = order / 2;

        int height = 1; // 叶子层
        int currentLevelNodes = leafNodes;

        while (currentLevelNodes > 1) {
            currentLevelNodes = (int) Math.ceil((double) currentLevelNodes / internalFanout);
            height++;
        }

        return height;
    }

    /**
     * 估算查询性能
     */
    public static QueryPerformance estimatePerformance(int totalRecords, int order) {
        int height = calculateHeight(totalRecords, order);
        int diskReads = height; // 每层一次磁盘读取

        // 假设每次磁盘读取耗时10ms
        long queryTimeMs = diskReads * 10;

        return new QueryPerformance(height, diskReads, queryTimeMs);
    }

    public static class QueryPerformance {
        public final int treeHeight;
        public final int diskReads;
        public final long estimatedTimeMs;

        public QueryPerformance(int height, int diskReads, long timeMs) {
            this.treeHeight = height;
            this.diskReads = diskReads;
            this.estimatedTimeMs = timeMs;
        }

        @Override
        public String toString() {
            return String.format("树高度: %d, 磁盘读取次数: %d, 预估查询时间: %dms",
                treeHeight, diskReads, estimatedTimeMs);
        }
    }
}

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

/**
 * 哈希索引实现（支持动态扩容）
 */
public class HashIndex<K, V> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final double DEFAULT_LOAD_FACTOR = 0.75;

    private Entry<K, V>[] table;
    private int size;
    private int threshold;
    private double loadFactor;

    @SuppressWarnings("unchecked")
    public HashIndex() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        this.table = new Entry[DEFAULT_INITIAL_CAPACITY];
        this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * loadFactor);
    }

    /**
     * 哈希表条目
     */
    static class Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next; // 链式解决冲突

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 哈希函数
     */
    private int hash(K key) {
        if (key == null) return 0;
        int h = key.hashCode();
        // 扰动函数，减少冲突
        h ^= (h >>> 16);
        return h & (table.length - 1);
    }

    /**
     * 插入操作
     */
    public V put(K key, V value) {
        if (size >= threshold) {
            resize();
        }

        return putInternal(key, value, table);
    }

    private V putInternal(K key, V value, Entry<K, V>[] targetTable) {
        int index = hash(key);
        Entry<K, V> entry = targetTable[index];

        // 查找是否已存在
        while (entry != null) {
            if (Objects.equals(entry.key, key)) {
                V oldValue = entry.value;
                entry.value = value;
                return oldValue;
            }
            entry = entry.next;
        }

        // 插入新条目
        targetTable[index] = new Entry<>(key, value, targetTable[index]);
        size++;
        return null;
    }

    /**
     * 查询操作 - O(1)平均时间复杂度
     */
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];

        while (entry != null) {
            if (Objects.equals(entry.key, key)) {
                return entry.value;
            }
            entry = entry.next;
        }

        return null;
    }

    /**
     * 动态扩容
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        Entry<K, V>[] oldTable = table;
        int newCapacity = oldTable.length * 2;

        table = new Entry[newCapacity];
        threshold = (int) (newCapacity * loadFactor);
        size = 0;

        // 重新哈希所有条目
        for (Entry<K, V> entry : oldTable) {
            while (entry != null) {
                Entry<K, V> next = entry.next;
                putInternal(entry.key, entry.value, table);
                entry = next;
            }
        }
    }

    /**
     * 删除操作
     */
    public V remove(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];
        Entry<K, V> prev = null;

        while (entry != null) {
            if (Objects.equals(entry.key, key)) {
                if (prev == null) {
                    table[index] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                size--;
                return entry.value;
            }
            prev = entry;
            entry = entry.next;
        }

        return null;
    }

    /**
     * 获取负载因子
     */
    public double getLoadFactor() {
        return (double) size / table.length;
    }

    /**
     * 获取冲突统计信息
     */
    public ConflictStatistics getConflictStatistics() {
        int emptyBuckets = 0;
        int maxChainLength = 0;
        int totalChainLength = 0;

        for (Entry<K, V> entry : table) {
            if (entry == null) {
                emptyBuckets++;
            } else {
                int chainLength = 0;
                Entry<K, V> current = entry;
                while (current != null) {
                    chainLength++;
                    current = current.next;
                }
                maxChainLength = Math.max(maxChainLength, chainLength);
                totalChainLength += chainLength;
            }
        }

        double avgChainLength = totalChainLength / (double) (table.length - emptyBuckets);
        return new ConflictStatistics(emptyBuckets, maxChainLength, avgChainLength);
    }

    public static class ConflictStatistics {
        public final int emptyBuckets;
        public final int maxChainLength;
        public final double avgChainLength;

        public ConflictStatistics(int emptyBuckets, int maxChainLength, double avgChainLength) {
            this.emptyBuckets = emptyBuckets;
            this.maxChainLength = maxChainLength;
            this.avgChainLength = avgChainLength;
        }

        @Override
        public String toString() {
            return String.format("空桶数: %d, 最大链长: %d, 平均链长: %.2f",
                emptyBuckets, maxChainLength, avgChainLength);
        }
    }
}

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

/**
 * 位图索引实现
 * 适用于性别、状态等低基数字段
 */
public class BitmapIndex {
    private final Map<String, BitSet> bitmaps;
    private int totalRecords;

    public BitmapIndex() {
        this.bitmaps = new HashMap<>();
        this.totalRecords = 0;
    }

    /**
     * 添加记录
     */
    public void addRecord(int recordId, String value) {
        BitSet bitmap = bitmaps.computeIfAbsent(value, k -> new BitSet());
        bitmap.set(recordId);
        totalRecords = Math.max(totalRecords, recordId + 1);
    }

    /**
     * 等值查询
     */
    public BitSet query(String value) {
        return bitmaps.getOrDefault(value, new BitSet());
    }

    /**
     * AND查询 - 多条件交集
     */
    public BitSet andQuery(String... values) {
        BitSet result = new BitSet();
        result.set(0, totalRecords); // 初始化为全1

        for (String value : values) {
            BitSet bitmap = bitmaps.get(value);
            if (bitmap != null) {
                result.and(bitmap);
            } else {
                result.clear(); // 如果某个值不存在，结果为空
                break;
            }
        }

        return result;
    }

    /**
     * OR查询 - 多条件并集
     */
    public BitSet orQuery(String... values) {
        BitSet result = new BitSet();

        for (String value : values) {
            BitSet bitmap = bitmaps.get(value);
            if (bitmap != null) {
                result.or(bitmap);
            }
        }

        return result;
    }

    /**
     * NOT查询 - 条件取反
     */
    public BitSet notQuery(String value) {
        BitSet bitmap = bitmaps.get(value);
        if (bitmap == null) {
            BitSet result = new BitSet();
            result.set(0, totalRecords);
            return result;
        }

        BitSet result = (BitSet) bitmap.clone();
        result.flip(0, totalRecords);
        return result;
    }

    /**
     * 复杂查询示例：(gender='M' AND status='active') OR age_group='young'
     */
    public BitSet complexQuery() {
        BitSet maleActive = andQuery("gender:M", "status:active");
        BitSet young = query("age_group:young");

        BitSet result = (BitSet) maleActive.clone();
        result.or(young);

        return result;
    }

    /**
     * 统计信息
     */
    public IndexStatistics getStatistics() {
        int totalBitmaps = bitmaps.size();
        long totalBits = bitmaps.values().stream()
            .mapToLong(bitmap -> bitmap.cardinality())
            .sum();

        double compressionRatio = (double) totalBits / (totalBitmaps * totalRecords);

        return new IndexStatistics(totalBitmaps, totalBits, compressionRatio);
    }

    public static class IndexStatistics {
        public final int totalBitmaps;
        public final long totalSetBits;
        public final double compressionRatio;

        public IndexStatistics(int totalBitmaps, long totalSetBits, double compressionRatio) {
            this.totalBitmaps = totalBitmaps;
            this.totalSetBits = totalSetBits;
            this.compressionRatio = compressionRatio;
        }

        @Override
        public String toString() {
            return String.format("位图数量: %d, 设置位总数: %d, 压缩比: %.2f",
                totalBitmaps, totalSetBits, compressionRatio);
        }
    }
}

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234

/**
 * 倒排索引实现 - 全文搜索核心
 */
public class InvertedIndex {
    private final Map<String, PostingsList> index;
    private final Map<Integer, DocumentInfo> documents;
    private final TextAnalyzer analyzer;

    public InvertedIndex() {
        this.index = new HashMap<>();
        this.documents = new HashMap<>();
        this.analyzer = new TextAnalyzer();
    }

    /**
     * 文档信息
     */
    static class DocumentInfo {
        final int docId;
        final String title;
        final String content;
        final int totalWords;

        DocumentInfo(int docId, String title, String content, int totalWords) {
            this.docId = docId;
            this.title = title;
            this.content = content;
            this.totalWords = totalWords;
        }
    }

    /**
     * 倒排链表
     */
    static class PostingsList {
        private final List<Posting> postings;

        PostingsList() {
            this.postings = new ArrayList<>();
        }

        void addPosting(int docId, int frequency, List<Integer> positions) {
            postings.add(new Posting(docId, frequency, positions));
        }

        List<Posting> getPostings() {
            return postings;
        }

        int getDocumentFrequency() {
            return postings.size();
        }
    }

    /**
     * 倒排记录
     */
    static class Posting {
        final int docId;
        final int termFrequency;
        final List<Integer> positions; // 词在文档中的位置

        Posting(int docId, int frequency, List<Integer> positions) {
            this.docId = docId;
            this.termFrequency = frequency;
            this.positions = new ArrayList<>(positions);
        }
    }

    /**
     * 文本分析器
     */
    static class TextAnalyzer {
        private final Set<String> stopWords;

        TextAnalyzer() {
            this.stopWords = Set.of("的", "了", "在", "是", "和", "与", "或", "但是", "然而");
        }

        List<String> analyze(String text) {
            return Arrays.stream(text.toLowerCase().split("[\\s\\p{Punct}]+"))
                .filter(word -> !word.isEmpty() && !stopWords.contains(word))
                .collect(Collectors.toList());
        }
    }

    /**
     * 添加文档
     */
    public void addDocument(int docId, String title, String content) {
        List<String> words = analyzer.analyze(title + " " + content);
        documents.put(docId, new DocumentInfo(docId, title, content, words.size()));

        // 统计词频和位置
        Map<String, List<Integer>> wordPositions = new HashMap<>();
        for (int i = 0; i < words.size(); i++) {
            String word = words.get(i);
            wordPositions.computeIfAbsent(word, k -> new ArrayList<>()).add(i);
        }

        // 更新倒排索引
        for (Map.Entry<String, List<Integer>> entry : wordPositions.entrySet()) {
            String term = entry.getKey();
            List<Integer> positions = entry.getValue();

            PostingsList postingsList = index.computeIfAbsent(term, k -> new PostingsList());
            postingsList.addPosting(docId, positions.size(), positions);
        }
    }

    /**
     * 单词查询
     */
    public List<Posting> search(String term) {
        PostingsList postingsList = index.get(term.toLowerCase());
        return postingsList != null ? postingsList.getPostings() : Collections.emptyList();
    }

    /**
     * 短语查询 - 查找连续词组
     */
    public List<Integer> phraseSearch(String phrase) {
        List<String> words = analyzer.analyze(phrase);
        if (words.size() < 2) {
            return search(words.get(0)).stream()
                .map(posting -> posting.docId)
                .collect(Collectors.toList());
        }

        // 获取所有词的倒排列表
        List<List<Posting>> allPostings = words.stream()
            .map(this::search)
            .collect(Collectors.toList());

        // 找到包含所有词的文档
        Set<Integer> candidateDocs = new HashSet<>();
        if (!allPostings.isEmpty()) {
            candidateDocs.addAll(allPostings.get(0).stream()
                .map(posting -> posting.docId)
                .collect(Collectors.toSet()));

            for (int i = 1; i < allPostings.size(); i++) {
                Set<Integer> currentDocs = allPostings.get(i).stream()
                    .map(posting -> posting.docId)
                    .collect(Collectors.toSet());
                candidateDocs.retainAll(currentDocs);
            }
        }

        // 验证短语的连续性
        List<Integer> results = new ArrayList<>();
        for (Integer docId : candidateDocs) {
            if (containsPhrase(docId, words, allPostings)) {
                results.add(docId);
            }
        }

        return results;
    }

    private boolean containsPhrase(int docId, List<String> words, List<List<Posting>> allPostings) {
        // 获取每个词在指定文档中的位置
        List<List<Integer>> wordPositions = new ArrayList<>();
        for (List<Posting> postings : allPostings) {
            List<Integer> positions = postings.stream()
                .filter(posting -> posting.docId == docId)
                .flatMap(posting -> posting.positions.stream())
                .sorted()
                .collect(Collectors.toList());
            wordPositions.add(positions);
        }

        // 检查是否存在连续的词组
        List<Integer> firstWordPositions = wordPositions.get(0);
        for (Integer startPos : firstWordPositions) {
            boolean isPhrase = true;
            for (int i = 1; i < words.size(); i++) {
                int expectedPos = startPos + i;
                if (!wordPositions.get(i).contains(expectedPos)) {
                    isPhrase = false;
                    break;
                }
            }
            if (isPhrase) {
                return true;
            }
        }

        return false;
    }

    /**
     * TF-IDF评分计算
     */
    public List<ScoredDocument> searchWithScore(String query) {
        List<String> queryTerms = analyzer.analyze(query);
        Map<Integer, Double> docScores = new HashMap<>();

        for (String term : queryTerms) {
            List<Posting> postings = search(term);
            if (postings.isEmpty()) continue;

            double idf = Math.log((double) documents.size() / postings.size());

            for (Posting posting : postings) {
                DocumentInfo doc = documents.get(posting.docId);
                double tf = (double) posting.termFrequency / doc.totalWords;
                double score = tf * idf;

                docScores.merge(posting.docId, score, Double::sum);
            }
        }

        return docScores.entrySet().stream()
            .map(entry -> new ScoredDocument(entry.getKey(), entry.getValue()))
            .sorted((a, b) -> Double.compare(b.score, a.score))
            .collect(Collectors.toList());
    }

    static class ScoredDocument {
        final int docId;
        final double score;

        ScoredDocument(int docId, double score) {
            this.docId = docId;
            this.score = score;
        }

        @Override
        public String toString() {
            return String.format("Doc %d (score: %.3f)", docId, score);
        }
    }
}