进行查找操作时,首先在根节点进行二分查找,找到key所在的指针,然后递归地在指
针所指向的节点进行查找。直到查找到叶子节点,然后在叶子节点上进行二分查找,找
出key所对应的数据项。
MySQL 数据库使用最多的索引类型是BTREE索引,底层基于B+树数据结构来实现。
mysql> show index from blog\G;
*************************** 1. row ***************************
Table: blog
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: blog_id
Collation: A
Cardinality: 4
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
Visible: YES
Expression: NULL
复制代码
哈希索引
哈希索引是基于哈希表实现的,对于每一行数据,存储引擎会对索引列进行哈希计算得
到哈希码,并且哈希算法要尽量保证不同的列值计算出的哈希码值是不同的,将哈希码
的值作为哈希表的key值,将指向数据行的指针作为哈希表的value值。这样查找一个数
据的时间复杂度就是O(1),一般多用于精确查找。