普通关系数据库通常用B树（特别是B+树）这种类型的数据结构来实现索引。B树和它的变种，如B+树、B*树，在数据库中的使用非常广泛，因为它们具有高效的搜索、插入和删除操作的特点，尤其是在处理大量数据时。
以下是一些关键点，解释了为什么B树（尤其是B+树）被广泛用于数据库索引：
- 平衡性：B树是一种平衡树，意味着所有叶子节点都位于同一层。这保证了从根节点到任何叶子节点的路径长度相同，因此每次查找操作的时间复杂度都是一致的。
- 分支因子：B树的一个节点可以有多个子节点（分支因子或阶数），这比二叉树的两个子节点要多得多。这降低了树的总体高度，从而减少了磁盘I/O操作的次数，这对于数据库中的大量数据是非常重要的。
- 磁盘友好：B树的设计能够很好地适应系统的磁盘访问特性。节点的大小通常设置为与磁盘块（页）的大小相匹配，这样每次磁盘I/O可以读取或写入完整的B树节点。
- 顺序访问优化：尤其是B+树，其所有的值都存储在叶子节点，并且叶子节点之间按顺序相连。这使得对数据进行顺序遍历变得非常高效，这在执行范围查询时非常有用。
- 最小化空间浪费：由于B树的节点通常很大，且每个节点存储多个键，这有助于减少未使用空间，同时保持树的平衡。
虽然B树是数据库索引的主流选择，但其他类型的数据结构也可能被使用，这取决于特定的应用场景和数据库的设计。例如，对于全文搜索，倒排索引可能会被使用；而对于地理空间数据，R树是更好的选择。哈希表也可能用于特殊情况下的索引，尤其是当查询完全基于等值查找时。