本文目录导读：
我来为你提供一个完整的Java索引优化案例,涵盖常用的数据结构索引和实际应用场景。
项目背景
假设我们正在开发一个电商系统的商品搜索功能,需要根据多种条件快速查询商品信息。
基础索引优化案例
HashMap索引优化
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
/**
* 商品索引管理器
*/
public class ProductIndexManager {
// 基础索引：按商品ID索引
private final Map<String, Product> productIdIndex = new ConcurrentHashMap<>();
// 二级索引：按商品分类索引
private final Map<String, Set<String>> categoryIndex = new ConcurrentHashMap<>();
// 价格区间索引
private final TreeMap<Double, Set<String>> priceIndex = new TreeMap<>();
/**
* 添加商品并建立索引
*/
public void addProduct(Product product) {
// 主索引
productIdIndex.put(product.getId(), product);
// 分类索引
categoryIndex.computeIfAbsent(
product.getCategory(),
k -> ConcurrentHashMap.newKeySet()
).add(product.getId());
// 价格索引
priceIndex.computeIfAbsent(
product.getPrice(),
k -> ConcurrentHashMap.newKeySet()
).add(product.getId());
}
/**
* 根据分类查询
*/
public List<Product> getProductsByCategory(String category) {
Set<String> ids = categoryIndex.getOrDefault(category, Collections.emptySet());
return ids.stream()
.map(productIdIndex::get)
.filter(Objects::nonNull)
.collect(Collectors.toList());
}
/**
* 根据价格范围查询
*/
public List<Product> getProductsByPriceRange(double min, double max) {
List<Product> result = new ArrayList<>();
SortedMap<Double, Set<String>> subMap = priceIndex.subMap(min, true, max, true);
for (Set<String> ids : subMap.values()) {
for (String id : ids) {
Product product = productIdIndex.get(id);
if (product != null) {
result.add(product);
}
}
}
return result;
}
/**
* 复合查询：分类+价格区间
*/
public List<Product> searchProducts(String category, double minPrice, double maxPrice) {
// 先从分类索引获取候选集
Set<String> categoryIds = categoryIndex.getOrDefault(category, Collections.emptySet());
// 从价格索引获取候选集
SortedMap<Double, Set<String>> priceSubMap = priceIndex.subMap(minPrice, true, maxPrice, true);
Set<String> priceIds = new HashSet<>();
for (Set<String> ids : priceSubMap.values()) {
priceIds.addAll(ids);
}
// 取交集
categoryIds.retainAll(priceIds);
// 获取详细信息
List<Product> result = new ArrayList<>();
for (String id : categoryIds) {
Product product = productIdIndex.get(id);
if (product != null) {
result.add(product);
}
}
return result;
}
}
/**
* 商品实体类
*/
class Product {
private String id;
private String name;
private String category;
private double price;
private int stock;
// getters and setters...
}
倒排索引优化
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
/**
* 商品搜索倒排索引
*/
public class InvertedIndex {
// 倒排索引：词 -> 商品ID列表
private final Map<String, Set<String>> invertedIndex = new ConcurrentHashMap<>();
// 商品ID -> 商品词汇
private final Map<String, Set<String>> productTerms = new ConcurrentHashMap<>();
// 存储商品信息
private final Map<String, Product> productStore = new ConcurrentHashMap<>();
/**
* 建立倒排索引
*/
public void indexProduct(Product product) {
// 解析商品名称和描述为词汇
Set<String> terms = analyzeText(product.getName() + " " + product.getDescription());
productTerms.put(product.getId(), terms);
// 更新倒排索引
for (String term : terms) {
invertedIndex.computeIfAbsent(term, k -> ConcurrentHashMap.newKeySet())
.add(product.getId());
}
productStore.put(product.getId(), product);
}
/**
* 搜索
*/
public List<Product> search(String query) {
Set<String> queryTerms = analyzeText(query);
if (queryTerms.isEmpty()) return Collections.emptyList();
// 获取包含所有查询词的文档集合
Set<String> resultIds = null;
for (String term : queryTerms) {
Set<String> termIds = invertedIndex.getOrDefault(term, Collections.emptySet());
if (resultIds == null) {
resultIds = new HashSet<>(termIds);
} else {
resultIds.retainAll(termIds); // AND操作
}
if (resultIds.isEmpty()) break;
}
// 转换为商品列表
return resultIds.stream()
.map(productStore::get)
.filter(Objects::nonNull)
.sorted(Comparator.comparing(Product::getPrice))
.collect(Collectors.toList());
}
/**
* 简单的分词器
*/
private Set<String> analyzeText(String text) {
return Arrays.stream(text.toLowerCase()
.split("[\\s,;:?!.]+"))
.filter(word -> word.length() > 1)
.collect(Collectors.toSet());
}
}
复合索引实现
import java.util.*;
import java.util.stream.Collectors;
/**
* 复合索引类
*/
public class CompositeIndex {
// 复合索引：分类+品牌 -> 商品列表
private final Map<String, Map<String, Set<String>>> compositeIndex = new HashMap<>();
// 商品存储
private final Map<String, Product> productStore = new ConcurrentHashMap<>();
/**
* 添加商品
*/
public void addProduct(Product product) {
productStore.put(product.getId(), product);
compositeIndex.computeIfAbsent(
product.getCategory(),
k -> new HashMap<>()
).computeIfAbsent(
product.getBrand(),
k -> ConcurrentHashMap.newKeySet()
).add(product.getId());
}
/**
* 利用复合索引查询
*/
public List<Product> findByCategoryAndBrand(String category, String brand) {
Map<String, Set<String>> brandMap = compositeIndex.getOrDefault(category, Collections.emptyMap());
Set<String> ids = brandMap.getOrDefault(brand, Collections.emptySet());
return ids.stream()
.map(productStore::get)
.filter(Objects::nonNull)
.collect(Collectors.toList());
}
/**
* 分类+价格排序
*/
public List<Product> findByCategorySortedByPrice(String category) {
// 获取该分类下所有商品
List<Product> products = new ArrayList<>();
Map<String, Set<String>> brandMap = compositeIndex.getOrDefault(category, Collections.emptyMap());
for (Set<String> ids : brandMap.values()) {
for (String id : ids) {
Product product = productStore.get(id);
if (product != null) {
products.add(product);
}
}
}
return products.stream()
.sorted(Comparator.comparing(Product::getPrice))
.collect(Collectors.toList());
}
}
LRU缓存索引优化
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
* LRU缓存索引
*/
public class LRUCacheIndex<K, V> {
private final LinkedHashMap<K, V> cache;
private final int capacity;
private final ReadWriteLock lock = new ReentrantReadWriteLock();
public LRUCacheIndex(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCacheIndex.this.capacity;
}
};
}
public V get(K key) {
lock.readLock().lock();
try {
return cache.get(key);
} finally {
lock.readLock().unlock();
}
}
public void put(K key, V value) {
lock.writeLock().lock();
try {
cache.put(key, value);
} finally {
lock.writeLock().unlock();
}
}
public boolean containsKey(K key) {
lock.readLock().lock();
try {
return cache.containsKey(key);
} finally {
lock.readLock().unlock();
}
}
public void clear() {
lock.writeLock().lock();
try {
cache.clear();
} finally {
lock.writeLock().unlock();
}
}
}
/**
* 使用LRU缓存的商品搜索
*/
public class ProductSearchService {
private final LRUCacheIndex<String, List<Product>> searchCache = new LRUCacheIndex<>(100);
private final ProductSearchEngine searchEngine = new ProductSearchEngine();
public List<Product> search(String query) {
// 检查缓存
List<Product> cached = searchCache.get(query);
if (cached != null) {
return cached;
}
// 执行搜索
List<Product> results = searchEngine.search(query);
// 放入缓存
searchCache.put(query, results);
return results;
}
/**
* 模拟搜索引擎
*/
private static class ProductSearchEngine {
public List<Product> search(String query) {
// 模拟搜索逻辑
List<Product> results = new ArrayList<>();
Product p = new Product();
p.setId("1");
p.setName("Test Product");
results.add(p);
return results;
}
}
}
布隆过滤器优化
import java.util.BitSet;
import java.util.concurrent.ConcurrentHashMap;
/**
* 布隆过滤器用于快速判断商品是否存在
*/
public class BloomFilter {
private final BitSet bitSet;
private final int size;
private final int hashFunctions;
private final ConcurrentHashMap<String, Product> productMap = new ConcurrentHashMap<>();
public BloomFilter(int size, int hashFunctions) {
this.size = size;
this.hashFunctions = hashFunctions;
this.bitSet = new BitSet(size);
}
/**
* 添加商品
*/
public void addProduct(Product product) {
productMap.put(product.getId(), product);
int[] hashes = hash(product.getId());
for (int hash : hashes) {
bitSet.set(Math.abs(hash % size), true);
}
}
/**
* 检查商品是否存在（可能有误判）
*/
public boolean mightContain(String productId) {
int[] hashes = hash(productId);
for (int hash : hashes) {
if (!bitSet.get(Math.abs(hash % size))) {
return false;
}
}
return true;
}
/**
* 获取商品（结合布隆过滤器）
*/
public Product getProduct(String productId) {
// 快速检查
if (!mightContain(productId)) {
return null; // 肯定不存在
}
// 可能存在，需要进一步确认
return productMap.get(productId);
}
/**
* 哈希函数
*/
private int[] hash(String key) {
int[] hashes = new int[hashFunctions];
for (int i = 0; i < hashFunctions; i++) {
hashes[i] = key.hashCode() * (i + 1) + i * 31;
}
return hashes;
}
}
空间索引优化
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
/**
* 空间索引（用于地理位置搜索）
*/
public class SpatialIndex {
// 使用格网索引
private final Map<String, Set<String>> gridIndex = new ConcurrentHashMap<>();
private final Map<String, Product> productMap = new ConcurrentHashMap<>();
// 格网大小（经纬度）
private static final double GRID_SIZE = 0.01;
/**
* 添加带位置信息的商品
*/
public void addProduct(Product product) {
if (product.getLatitude() != null && product.getLongitude() != null) {
String gridKey = getGridKey(product.getLatitude(), product.getLongitude());
gridIndex.computeIfAbsent(gridKey, k -> ConcurrentHashMap.newKeySet())
.add(product.getId());
}
productMap.put(product.getId(), product);
}
/**
* 查找附近商品
*/
public List<Product> findNearby(double latitude, double longitude, double radiusKm) {
List<Product> results = new ArrayList<>();
// 计算搜索范围
double latRange = radiusKm / 111.0; // 纬度范围
double lonRange = radiusKm / (111.0 * Math.cos(Math.toRadians(latitude))); // 经度范围
// 获取覆盖的格网
String minGrid = getGridKey(latitude - latRange, longitude - lonRange);
String maxGrid = getGridKey(latitude + latRange, longitude + lonRange);
// 遍历相关格网
for (String key : gridIndex.keySet()) {
if (isWithinGridRange(key, minGrid, maxGrid)) {
Set<String> ids = gridIndex.get(key);
for (String id : ids) {
Product product = productMap.get(id);
if (product != null &&
calculateDistance(latitude, longitude,
product.getLatitude(), product.getLongitude()) <= radiusKm) {
results.add(product);
}
}
}
}
return results;
}
/**
* 计算两个位置的距离（km）
*/
private double calculateDistance(double lat1, double lon1, double lat2, double lon2) {
double R = 6371; // 地球半径（km）
double latDistance = Math.toRadians(lat2 - lat1);
double lonDistance = Math.toRadians(lon2 - lon1);
double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
+ Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
* Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return R * c;
}
/**
* 获取格网键值
*/
private String getGridKey(double lat, double lon) {
int latGrid = (int) Math.floor(lat / GRID_SIZE);
int lonGrid = (int) Math.floor(lon / GRID_SIZE);
return latGrid + "," + lonGrid;
}
/**
* 判断格网是否在范围内
*/
private boolean isWithinGridRange(String key, String minKey, String maxKey) {
String[] parts = key.split(",");
String[] minParts = minKey.split(",");
String[] maxParts = maxKey.split(",");
int lat = Integer.parseInt(parts[0]);
int lon = Integer.parseInt(parts[1]);
int minLat = Integer.parseInt(minParts[0]);
int maxLat = Integer.parseInt(maxParts[0]);
int minLon = Integer.parseInt(minParts[1]);
int maxLon = Integer.parseInt(maxParts[1]);
return lat >= minLat && lat <= maxLat && lon >= minLon && lon <= maxLon;
}
}
使用示例
public class IndexOptimizationDemo {
public static void main(String[] args) {
// 1. 基础索引示例
ProductIndexManager indexManager = new ProductIndexManager();
// 添加商品
for (int i = 0; i < 1000; i++) {
Product product = new Product();
product.setId("P" + i);
product.setName("Product " + i);
product.setCategory(i % 10 == 0 ? "电子产品" : "日用品");
product.setPrice(10.0 + i * 0.5);
indexManager.addProduct(product);
}
// 查询示例
List<Product> electronics = indexManager.getProductsByCategory("电子产品");
System.out.println("电子产品数量: " + electronics.size());
// 价格查询
List<Product> priceRange = indexManager.getProductsByPriceRange(100, 200);
System.out.println("价格100-200的商品数量: " + priceRange.size());
// 2. 倒排索引示例
InvertedIndex invertedIndex = new InvertedIndex();
// 添加一些商品
for (int i = 0; i < 100; i++) {
Product product = new Product();
product.setId("P" + i);
product.setName("智能手机 iPhone 13 Pro");
product.setDescription("高端智能手机");
invertedIndex.indexProduct(product);
}
// 搜索
List<Product> searchResult = invertedIndex.search("智能手机");
System.out.println("搜索'智能手机'结果: " + searchResult.size());
// 3. 缓存索引示例
ProductSearchService searchService = new ProductSearchService();
List<Product> cachedResult = searchService.search("热门商品");
// 4. 布隆过滤器示例
BloomFilter bloomFilter = new BloomFilter(100000, 5);
Product product = new Product();
product.setId("ABC123");
bloomFilter.addProduct(product);
boolean exists = bloomFilter.mightContain("ABC123"); // true
boolean notExists = bloomFilter.mightContain("XYZ789"); // 可能false
System.out.println("商品存在: " + exists);
}
}
优化要点总结
-
索引选择原则
- 根据查询模式选择合适的索引结构
- 对于频繁查询的字段建立索引
- 考虑索引的更新和维护成本
-
内存优化
- 使用ConcurrentHashMap支持并发访问
- 使用缓存机制减少重复计算
- 合理设置缓存大小
-
查询优化
- 结合多个索引进行复合查询
- 使用布隆过滤器进行快速过滤
- 采用缓存策略提高响应速度
-
性能监控
- 记录索引命中率
- 监控索引维护时间
- 定期进行索引优化
-
扩展性考虑
- 支持动态扩展
- 考虑分布式场景
- 预留接口以便后续优化
这个案例涵盖了Java中常见的数据结构和索引优化技术,可以根据实际业务需求进行调整和扩展。
