哈希表、有序数组和搜索树。哈希表这种结构适用于只有等值查询的场景
有序数组在等值查询和范围查询场景中的性能就都非常优秀
有序数组索引只适用于静态存储引擎
索引
索引的作用:为了提高查询的效率
常见的索引数据模型
1.哈希,2.有序数组 ,3.搜索树
哈希表
原理:把值放到一个数组里面,用一各哈希函数把key换算成确切位置,将值放进去.
hash冲突:链表,效率慢
特点:等值查询效率高,不适用区间查询
有序数组
原理:索引是一个有序递增的数组,事件复杂度 O(log(n))
缺点:修改操作资源耗费巨大
优点:等值查询和范围查询多很好,适用静态的,不会频繁修改的数据,
搜索树
>1.二叉搜索树
二叉搜索树:每个左子树值小于父节点值,父节点有小于右子树的值
二叉搜索树:查询时间复杂度是O(log(n)),更新复杂度也是O(log(n))(需要维护树结构)
数据库索引不适用二叉树,因为会导致层级过高,数据块过多,查询时需要访问的磁盘次数增加
数据库多使用N叉树
InnoDB
InnoDB中的常用索引模型：B+Tree
索引类型：主键索引、非主键索引
主键索引的叶子节点存的是整行的数据(聚簇索引)，非主键索引的叶子节点内容是主键的值(二级索引)
主键索引和普通索引的区别：主键索引只要搜索ID这个B+Tree即可拿到数据。普通索引先搜索索引拿到主键值，再到主键索引树搜索一次(回表)
一个数据页满了，按照B+Tree算法，新增加一个数据页，叫做页分裂，会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并，合并的过程是分裂过程的逆过程。
从性能和存储空间方面考量，自增主键往往是更合理的选择。(因为空间小,数据页不会分裂)
网友评论