索引的三种常见底层数据结构以及优缺点？

索引在数据库中有三种常见的底层数据结构：**哈希表**、**有序数组** 和 **搜索树**（如 B+ 树）。每种结构在不同的场景下有其优势和劣势，下面详细说明这些数据结构的特点及其在数据库索引中的优缺点。 ### 1. 哈希表（Hash Table） #### 优点： - **查询速度快**：哈希表基于键的哈希值直接定位到数据，时间复杂度为 O(1)，非常适合等值查询（如 `=`、`IN` 等）。 - **简单高效**：对于频繁的等值查询操作，哈希索引非常高效。 #### 缺点： - **不支持范围查询**：哈希表只能用于精确查找，无法处理范围查询（如 `BETWEEN`、`>`、`<` 等）。 - **数据有序性差**：哈希表中的数据没有按照任何顺序存储，因此无法用于排序查询。 - **哈希冲突**：虽然有冲突解决机制，但大量冲突会影响性能。 #### 适用场景： - 哈希索引适合等值查询的场景，比如在 `Memcached`、Redis 以及部分 NoSQL 引擎中使用较多，不适合范围查询。 ### 2. 有序数组（Ordered Array） #### 优点： - **查询性能高**：对于静态数据集，等值查询和范围查询的性能非常高。通过二分查找，时间复杂度为 O(log n)。 - **范围查询快**：因为数据是有序的，范围查询（如 `BETWEEN` 操作）可以快速定位区间的起点和终点，然后顺序扫描，效率高。 #### 缺点： - **更新性能差**：数组是有序的，每次插入或删除操作需要移动大量数据，更新代价高，时间复杂度为 O(n)。 - **仅适用于静态数据**：由于插入、删除、更新的成本高，有序数组更适合静态数据存储，数据变化不频繁的场景。 #### 适用场景： - 适用于查询多、更新少的静态场景，如一些报表系统中数据更新较少、查询较多的情况。 ### 3. 搜索树（N 叉树，通常是 B+ 树） **B+ 树** 是数据库中最常用的索引结构之一，也是 MySQL InnoDB 存储引擎的默认索引结构。 #### 优点： - **读写性能优秀**：B+ 树通过在叶子节点中顺序存储数据，保证了良好的范围查询性能，并且支持等值查询。查询、插入和删除的时间复杂度都为 O(log n)。 - **适配磁盘访问**：B+ 树是一个 N 叉树，节点存储大量的键值对，树的高度较低，减少了磁盘 I/O 操作，特别适合磁盘存储。 - **支持范围查询和排序**：B+ 树的叶子节点按顺序排列，适合范围查询、排序查询。 #### 缺点： - **内存开销相对较大**：为了保持数据的有序性，B+ 树需要在节点之间维护额外的指针，且在更新时可能导致树的分裂和合并。 - **重建成本较高**：当数据量特别大时，重建索引的成本较高。 #### 适用场景： - B+ 树广泛应用于数据库系统中，适合大部分查询场景，尤其是需要同时支持等值查询、范围查询、排序查询等多种操作的应用场景。MySQL InnoDB 使用 B+ 树作为默认的索引结构。 ### 扩展：以 InnoDB 中 B+ 树为例 - 在 InnoDB 中，B+ 树索引的每个节点最多可以存储大约 1200 个索引条目。如果 B+ 树的高度为 4，那么可以存储约 1200^3（约 17 亿）个值。 - 对于一个 10 亿行的表，查找一个值最多只需要 3 次磁盘 I/O，因为树的根节点总是保存在内存中，而第二层节点也很可能常驻内存，因此实际磁盘访问次数更少。 总结来说： - **哈希表** 适合等值查询，但不支持范围查询。 - **有序数组** 适合静态数据的高效查询，但更新性能差。 - **B+ 树** 由于其读写性能和适应磁盘访问的特点，成为数据库中广泛应用的索引结构，适用于大部分场景。