B树家族深度解析：从B树到LSM树的数据结构演进

技术背景

B树是一种自平衡的搜索树，广泛用于数据库和文件系统中。它通过减少磁盘I/O次数，实现了高效的数据存储和检索。随着数据库技术的发展，B树衍生出了B+树、B*树，以及与LSM树等新兴数据结构的竞争。

B树基础

1. B树的定义

B树是一种多路搜索树，具有以下特性：

• 每个节点最多有 m 个子节点（m 阶）
• 根节点至少有 2 个子节点（除非是叶子节点）
• 所有内部节点（除根和叶子）至少有 ⌈m/2⌉ 个子节点
• 所有叶子节点在同一层
• 节点中的键按升序排列

2. B树的结构

        [50]
       /    \
   [20,30]  [60,80]
   /  |   \   /  |  \
[10][25][35][55][70][90]
​

3. B树的实现

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []
        
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t  # 最小度数
        
    def search(self, k, node=None):
        if node is None:
            node = self.root
            
        i = 0
        while i < len(node.keys) and k > node.keys[i]:
            i += 1
            
        if i < len(node.keys) and k == node.keys[i]:
            return (node, i)
        elif node.leaf:
            return None
        else:
            return self.search(k, node.child[i])
    
    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode()
            new_root.child.append(self.root)
            self.split_child(new_root, 0)
            self.root = new_root
            self.insert_non_full(new_root, k)
        else:
            self.insert_non_full(root, k)
    
    def split_child(self, parent, i):
        t = self.t
        y = parent.child[i]
        z = BTreeNode(y.leaf)
        
        parent.child.insert(i + 1, z)
        parent.keys.insert(i, y.keys[t - 1])
        
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        
        if not y.leaf:
            z.child = y.child[t: 2 * t]
            y.child = y.child[0: t]
    
    def insert_non_full(self, node, k):
        i = len(node.keys) - 1
        
        if node.leaf:
            node.keys.append(0)
            while i >= 0 and k < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = k
        else:
            while i >= 0 and k < node.keys[i]:
                i -= 1
            i += 1
            
            if len(node.child[i].keys) == (2 * self.t) - 1:
                self.split_child(node, i)
                if k > node.keys[i]:
                    i += 1
            
            self.insert_non_full(node.child[i], k)
​

B+树

1. B+树的特点

B+树是B树的变体，具有以下特点：

• 所有键值都存储在叶子节点
• 内部节点只存储索引
• 叶子节点通过指针连接，支持范围查询
• 更适合磁盘存储

2. B+树的结构

        [30, 60]
       /    |    \
   [20]   [50]   [70, 80]
    |      |       |
  [20]   [50]   [70, 80]
    ↓      ↓       ↓
[10,30] [55] [65,75,90]
​

3. B+树的实现

class BPlusTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []
        self.next = None  # 叶子节点链表指针
        
class BPlusTree:
    def __init__(self, order):
        self.root = BPlusTreeNode(True)
        self.order = order
        
    def search(self, key):
        return self._search(self.root, key)
    
    def _search(self, node, key):
        if node.leaf:
            for i, k in enumerate(node.keys):
                if k == key:
                    return (node, i)
            return None
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            return self._search(node.child[i], key)
    
    def range_query(self, start_key, end_key):
        result = []
        leaf = self._find_leaf(start_key)
        
        while leaf and leaf.keys[0] <= end_key:
            for key in leaf.keys:
                if start_key <= key <= end_key:
                    result.append(key)
            leaf = leaf.next
            
        return result
    
    def _find_leaf(self, key):
        node = self.root
        while not node.leaf:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            node = node.child[i]
        return node
​

4. B+树的应用

MySQL InnoDB 索引

-- 创建 B+树索引
CREATE INDEX idx_user_email ON users(email);

-- 范围查询（B+树的优势）
SELECT * FROM users 
WHERE email BETWEEN 'a@example.com' AND 'f@example.com';

-- 分析索引使用
EXPLAIN SELECT * FROM users WHERE email = 'user@example.com';
​

B*树

1. B*树的特点

B*树是B树的进一步优化：

• 节点至少 2/3 满（而不是 1/2）
• 节点满时尝试重新分配，而不是立即分裂
• 更好的空间利用率
• 减少树的高度

2. B*树的实现

class BStarTree(BTree):
    def __init__(self, t):
        super().__init__(t)
        
    def insert(self, k):
        # B*树的插入逻辑更复杂
        # 优先尝试重新分配节点
        root = self.root
        
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode()
            new_root.child.append(self.root)
            self.redistribute(new_root, 0)
            self.root = new_root
            self.insert_non_full(new_root, k)
        else:
            self.insert_non_full(root, k)
    
    def redistribute(self, parent, i):
        # 尝试从兄弟节点重新分配键
        if i > 0 and len(parent.child[i - 1].keys) > self.t - 1:
            # 从左兄弟借
            self.borrow_from_left(parent, i)
        elif i < len(parent.child) - 1 and len(parent.child[i + 1].keys) > self.t - 1:
            # 从右兄弟借
            self.borrow_from_right(parent, i)
        else:
            # 必须分裂
            self.split_child(parent, i)
​

LSM树

1. LSM树的原理

LSM（Log-Structured Merge）树采用不同的策略：

• 所有写入先进入内存表（MemTable）
• 内存表满时刷到磁盘（SSTable）
• 后台合并和压缩 SSTable
• 优化写入性能，牺牲部分读取性能

2. LSM树的架构

写入请求 → MemTable (内存)
     ↓
   满 (64MB)
     ↓
   Immutable MemTable
     ↓
   SSTable (Level 0)
     ↓
   Compaction
     ↓
   SSTable (Level 1)
     ↓
   SSTable (Level N)
​

3. LSM树的实现

import bisect
import pickle

class MemTable:
    def __init__(self, max_size=64000000):  # 64MB
        self.data = []
        self.max_size = max_size
        self.current_size = 0
        
    def put(self, key, value):
        # 使用跳表或有序数组
        bisect.insort(self.data, (key, value))
        self.current_size += len(key) + len(value)
        
    def get(self, key):
        i = bisect.bisect_left(self.data, (key, ''))
        if i < len(self.data) and self.data[i][0] == key:
            return self.data[i][1]
        return None
    
    def is_full(self):
        return self.current_size >= self.max_size

class SSTable:
    def __init__(self, filename):
        self.filename = filename
        self.index = self._build_index()
        
    def _build_index(self):
        # 为 SSTable 构建稀疏索引
        index = {}
        with open(self.filename, 'rb') as f:
            while True:
                pos = f.tell()
                try:
                    key_len = int.from_bytes(f.read(4), 'big')
                    key = f.read(key_len).decode('utf-8')
                    value_len = int.from_bytes(f.read(4), 'big')
                    f.read(value_len)
                    
                    # 每 1000 个键建立索引
                    if len(index) % 1000 == 0:
                        index[key] = pos
                except:
                    break
        return index
    
    def get(self, key):
        # 使用稀疏索引定位块
        keys = sorted(self.index.keys())
        i = bisect.bisect_right(keys, key) - 1
        
        if i >= 0:
            start_pos = self.index[keys[i]]
            with open(self.filename, 'rb') as f:
                f.seek(start_pos)
                while True:
                    try:
                        pos = f.tell()
                        key_len = int.from_bytes(f.read(4), 'big')
                        current_key = f.read(key_len).decode('utf-8')
                        value_len = int.from_bytes(f.read(4), 'big')
                        value = f.read(value_len).decode('utf-8')
                        
                        if current_key == key:
                            return value
                        elif current_key > key:
                            break
                    except:
                        break
        return None

class LSMTree:
    def __init__(self, data_dir='data'):
        self.memtable = MemTable()
        self.immutable_memtable = None
        self.sstables = []
        self.data_dir = data_dir
        self.level = 0
        
    def put(self, key, value):
        self.memtable.put(key, value)
        
        if self.memtable.is_full():
            self.flush()
    
    def get(self, key):
        # 先查 MemTable
        value = self.memtable.get(key)
        if value is not None:
            return value
        
        # 再查 Immutable MemTable
        if self.immutable_memtable:
            value = self.immutable_memtable.get(key)
            if value is not None:
                return value
        
        # 最后查 SSTables（从新到旧）
        for sstable in reversed(self.sstables):
            value = sstable.get(key)
            if value is not None:
                return value
        
        return None
    
    def flush(self):
        # 切换 MemTable
        self.immutable_memtable = self.memtable
        self.memtable = MemTable()
        
        # 写入 SSTable
        filename = f"{self.data_dir}/sstable_{len(self.sstables)}.db"
        self._write_sstable(filename, self.immutable_memtable.data)
        
        # 创建 SSTable
        sstable = SSTable(filename)
        self.sstables.append(sstable)
        
        # 触发压缩
        if len(self.sstables) > 10:
            self.compact()
        
        self.immutable_memtable = None
    
    def _write_sstable(self, filename, data):
        with open(filename, 'wb') as f:
            for key, value in sorted(data):
                key_bytes = key.encode('utf-8')
                value_bytes = value.encode('utf-8')
                
                f.write(len(key_bytes).to_bytes(4, 'big'))
                f.write(key_bytes)
                f.write(len(value_bytes).to_bytes(4, 'big'))
                f.write(value_bytes)
    
    def compact(self):
        # 多路归并 SSTables
        # 简化版本：合并所有 SSTable
        merged_data = []
        
        for sstable in self.sstables:
            with open(sstable.filename, 'rb') as f:
                while True:
                    try:
                        key_len = int.from_bytes(f.read(4), 'big')
                        key = f.read(key_len).decode('utf-8')
                        value_len = int.from_bytes(f.read(4), 'big')
                        value = f.read(value_len).decode('utf-8')
                        bisect.insort(merged_data, (key, value))
                    except:
                        break
        
        # 去重（保留最新的值）
        seen = set()
        unique_data = []
        for key, value in reversed(merged_data):
            if key not in seen:
                unique_data.append((key, value))
                seen.add(key)
        unique_data.reverse()
        
        # 写入新的 SSTable
        filename = f"{self.data_dir}/sstable_compacted.db"
        self._write_sstable(filename, unique_data)
        
        # 更新 SSTables 列表
        for sstable in self.sstables:
            os.remove(sstable.filename)
        self.sstables = [SSTable(filename)]
​

性能对比

1. 读写性能

2. 空间利用率

3. 适用场景

B+树适合：

• 读多写少
• 需要强一致性
• 范围查询频繁
• 传统的OLTP系统

LSM树适合：

• 写多读少
• 大数据量
• 写入吞吐要求高
• 日志、时序数据

实际应用

1. MySQL InnoDB (B+树)

-- InnoDB 使用 B+树索引
-- 聚簇索引（主键）
ALTER TABLE users ADD PRIMARY KEY (id);

-- 辅助索引
CREATE INDEX idx_email ON users(email);

-- 复合索引
CREATE INDEX idx_name_age ON users(name, age);
​

2. LevelDB (LSM树)

import plyvel

# 创建数据库
db = plyvel.DB('./leveldb', create_if_missing=True)

# 写入
db.put(b'key1', b'value1')
db.put(b'key2', b'value2')

# 读取
value = db.get(b'key1')

# 批量写入
wb = db.write_batch()
wb.put(b'key3', b'value3')
wb.put(b'key4', b'value4')
wb.write()

# 范围查询
for key, value in db.iterator(start=b'key1', stop=b'key3'):
    print(f"{key}: {value}")

# 关闭
db.close()
​

3. RocksDB (优化的LSM树)

#include <rocksdb/db.h>

// 打开数据库
rocksdb::DB* db;
rocksdb::Options options;
options.create_if_missing = true;
rocksdb::Status status = rocksdb::DB::Open(options, "/path/to/db", &db);

// 写入
status = db->Put(rocksdb::WriteOptions(), "key1", "value1");

// 读取
std::string value;
status = db->Get(rocksdb::ReadOptions(), "key1", &value);

// 批量写入
rocksdb::WriteBatch batch;
batch.Put("key2", "value2");
batch.Put("key3", "value3");
status = db->Write(rocksdb::WriteOptions(), &batch);

// 删除
status = db->Delete(rocksdb::WriteOptions(), "key1");

// 关闭
delete db;
​

优化技巧

1. B+树优化

-- 前缀索引（减少索引大小）
CREATE INDEX idx_email_prefix ON users(email(10));

-- 覆盖索引（避免回表）
CREATE INDEX idx_covering ON users(name, age, email);

-- 索引选择性优化
-- 选择性高的列建索引
SELECT COUNT(DISTINCT column) / COUNT(*) FROM table;
​

2. LSM树优化

# 布隆过滤器加速查找
from pybloom_live import ScalableBloomFilter

class SSTableWithBloom(SSTable):
    def __init__(self, filename):
        super().__init__(filename)
        self.bloom_filter = self._build_bloom_filter()
    
    def _build_bloom_filter(self):
        bloom = ScalableBloomFilter(initial_capacity=1000000, error_rate=0.001)
        
        with open(self.filename, 'rb') as f:
            while True:
                try:
                    key_len = int.from_bytes(f.read(4), 'big')
                    key = f.read(key_len).decode('utf-8')
                    value_len = int.from_bytes(f.read(4), 'big')
                    f.read(value_len)
                    bloom.add(key)
                except:
                    break
        return bloom
    
    def get(self, key):
        if key not in self.bloom_filter:
            return None  # 确定不存在
        return super().get(key)
​

总结

B树家族各有优势：

✅ B+树：读优化，适合传统数据库
✅ LSM树：写优化，适合大数据和时序数据
✅ 选择标准：根据读写比例和数据规模选择

理解这些数据结构的特点和适用场景，对于设计和优化高性能存储系统至关重要。