什么是索引，用的什么数据结构

索引是一种数据结构，用于加快数据库或文件系统中数据的查找速度。它可以将数据按照某种规则进行排序和组织，以便快速地定位和访问数据。在数据库中，索引通常由一个或多个列组成，每个列都有对应的排序规则和查找方式。

常用的索引数据结构有B树、B+树和哈希表。其中，B树和B+树是基于磁盘存储的索引结构，适用于大型数据库中的数据查找；哈希表则是内存中的索引结构，适用于小型数据集的快速查找。B树和B+树的区别在于B+树将所有的数据都存储在叶子节点中，而非叶子节点仅存储索引信息，这样可以减少磁盘I/O操作，提高查询效率。哈希表则是通过哈希函数将数据映射到一个固定的桶中，然后在桶中查找数据，因此查询速度非常快，但是哈希表的缺点是不支持范围查找和排序操作。