数据索引

简介: 数据索引

索引常见模型

先介绍比较常见简单的数据索引:哈希表、有序数组、搜索树

哈希表

哈希表是一种以键值存储数据的结构,只用输入key就能找到value。

哈希表就是把key放在一个位置,把值经过计算均匀的分布在数组里,多个 key 值经过哈希函数的换算,会出现同一个值的情况。处理这种情况的一种方法是,拉出一个链表。

例如你需要在哈希值为2的链表里面新增一个值,直接在尾部添加就好了,但如果需要在里面查询某一个值,你得扫描里面所有的值,因为链表不是有序的。

哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些NoSQL 引擎。

有序数组

有序数组按数组递增的顺序排序,如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。

搜索树

二叉搜索树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。

二叉树搜索效率最高,但是数据存储不使用二叉树,因为索引可能还要写入磁盘中,因为是二叉,数据量大的情况下树高可能有几十,相当于几十个数据块,而磁盘读取一个数据块需要花费10ms,相对来说查询太慢了。

树可以有二叉也可以有多叉,每个节点下面有多个儿子,N叉树用很低的树高,存储庞大的数据,减少对磁盘的访问,被广泛用于数据库中。

B+树类似于多叉树,不过可以在最后的子节点用双向链表连了起来,比如我只需要找到8-10这个区间,然后通过8往后面遍历找到后面的9。

这样它完美地支持了我们提的三个需求:快速查找值,区间,顺序逆序查找。

索引维护

在插入新值的时候,需要往后挪动位置,但是刚刚数据已经满了,只能开启新的一页,根据 B+ 树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂,会影响性能。

如果是以自增 id 作为主键,由于新插入的表中生成的 id 比索引中所有的值都大,所以它要么合到已存在的节点(元素个数未满)中,要么放入新建的节点中(如下图示)所以如果是以自增 id 作为主键,就不存在页分裂的问题了。

也会有页合并的情况,删掉了两个数据,数据分散在两个不同的节点上,可能造成两次 IO 读,势必会影响查找效率! 那什么时候会发生页合并呢,我们可以定个阈值,比如对于 N 叉树来说,当节点的个数小于 N/2 的时候就应该和附近的节点合并,不过需要注意的是合并后节点里的元素大小可能会超过 N,造成页分裂,需要再对父节点等进行调整以让它满足 N 叉树的条件。

假如有很长的身份证,还是用ID作为主键呢,答案肯定是用ID,因为索引越长占用空间越大。


相关文章
|
索引
索引
索引。
81 0
|
4月前
|
TensorFlow 算法框架/工具 索引
索引
【8月更文挑战第13天】索引。
30 1
|
7月前
|
存储 NoSQL 关系型数据库
索引!索引!!索引!!!到底什么是索引?
**索引是数据库中的数据结构,类似书籍目录,加速数据查找和访问。优点包括提升查询性能、数据检索速度、支持唯一性约束及优化排序和连接操作。缺点在于增加写操作开销、占用存储空间、高维护成本和过多索引可能降低性能。常见的索引类型有单值、复合、唯一、聚集和非聚集索引等,实现方式涉及B树、B+树和哈希表。B树和B+树适合磁盘存储,B+树尤其适用于范围查询,哈希索引则适用于快速等值查询。**
65 0
|
7月前
|
SQL 搜索推荐 关系型数据库
|
7月前
|
SQL 关系型数据库 MySQL
关于索引的使用
关于索引的使用
|
7月前
|
安全 关系型数据库 MySQL
合理使用索引
【5月更文挑战第9天】这篇文章探讨了数据库索引的高效使用,包括函数和表达式索引、查找和删除未使用的索引、安全删除索引、多列索引策略、部分索引以及针对通配符搜索、排序、散列和降序索引的特殊技巧。还介绍了部分索引在减少索引大小和处理唯一性约束中的应用,以及PostgreSQL对前导通配符搜索的支持。通过遵循简单的多列索引规则和利用特定类型的索引,如哈希和降序索引,可以显著提高查询性能。
110 0
|
存储 关系型数据库 MySQL
了解和认识索引
了解和认识索引 。
64 0
|
7月前
|
存储 算法 关系型数据库
索引总结(2)
索引总结(2)
50 0
|
关系型数据库 MySQL 数据库
了解和认识索引
了解和认识索引。
56 0
|
关系型数据库 MySQL 索引
索引(2)
索引(2)。
45 0