高性能B-tree索引

高性能 B-tree 索引

摘要

在关系型数据库系统（RDBMS）中，索引是一个重要组成部分，其主要作用是提升查询性能，侧重OLTP的关系型数据库常用的索引大致可以分为两大类：

• 基于树（tree-based）的B-tree索引。B-tree索引（这里B-tree代表B+-tree）适合以块或者页为单位的存储，支持高效的点查询（point query）和范围查询（range query），在数据库中已经广泛使用。
• 基于哈希(hash-based)的哈希索引。哈希索引更适合建在内存中，仅支持点查询，更多使用于内存数据库中，如MS SQL Server Hekaton, SAP ASE In Memory Row Store等。

目前主流数据库产品大都支持B-tree索引， B-tree索引的设计和实现至关重要，直接影响整个数据库系统的性能，本文主要关注高性能B-tree索引在数据库中的设计和实现。