首页  思维导图  详情

【数据】数据结构，数据查询，排序

2025-01-07 10:11:39   0  举报





AI智能生成

数据结构，数据算法面试问题；实战数据查询，排序等常见底层基础问题

数据结构

算法

排序

检索

数据库

作者其他创作

大纲/内容

关系型数据库 RDB

https://www.processon.com/view/61e02ffde0b34d1be7f16460

非关系型（文档）数据库

https://www.processon.com/view/61e02ffde0b34d1be7f16460

键值数据库

https://www.processon.com/view/6751753423bb5e5f8d18309f

搜索型数据库

https://www.processon.com/view/677b45913faeda177b462eda

存储问题

数据结构

一维线性结构

顺序表

顺序表可以实现下标的快速访问

顺序表在中间或者头部插入节点和删除节点必须依次挪动节点

顺序表每次增容固定大小的空间有可能造成空间浪费，但不用每次插入时都动态开辟空间

队列

先进先出

应用

排队问题

事件驱动

堆栈

先进后出

应用

历史记录

括号匹配问题

链表

单项链表

单链表必须从头依次遍历查找，时间复杂度为O(n)

单链表插入、删除节点快，时间复杂度为O(1)

单链表每次插入节点时都必须动态开辟空间、删除节点时必须释放掉动态开辟的空间

应用

升级循环单项链表

花名册录入

循环单项链表

双向链表

回顾回述问题

节点可以向前查找，向后查找

应用

升级循环双向链表

回顾回述问题

循环双向链表

二维树状结构

hash结构

结构

哈希表首先定义链结点Node。其中Node有三个属性，一个是key，一个value，还有一个是对应链表的point

连续空间中顺序键值对-->链表

特点

信息压缩

插入快速

hash碰撞

范围查询难

排序难

平衡二叉树

结构

左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

特点

插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)

树的深度高了以后，回述和查询效率大大下降

AVL树

结构

由于二叉搜索树在最坏的情况下（顺序写入）会退化成链表，搜索时的时间复杂度高

这里AVL树在节点进行插入、删除、修改的时候进行了自平衡，让整棵树不至于过于倾斜

树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

某结点的左子树与右子树的高度（深度）差即为该结点的平衡因子（BF、Balance Factor）

图示

右边二叉树中节点值为10的左右子树高度差为2

自平衡手段

如果插入新节点时发现左右子树的平衡因子的绝对值大于2，通过LL、LR、RR、RL的操作保证平衡因子的绝对值小于等于1

特点

AVL树由于自平衡的存在，使得树的高度不会太高，平均搜索的时间复杂度为O(logN)

树的高度较高，需要多次IO操作

B树

结构

B树属于多叉树又名平衡多路查找树

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则

子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉树）

特点

每个节点包含的关键字增多了，在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理

树的节点关键字增多后，树的层级比原来的二叉树少了，减少数据查找的时间复杂度

B+树

结构

B+树是B树的一个升级版

B+树的非叶子节点不保存关键字记录的指针，只进行数据索引

B+树叶子节点保存了父节点的所有关键字记录的指针

B+树叶子节点的关键字从小到大有序排列，相互双向指针

特点

B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多

B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表

B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可

B*树

结构

B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）

每个节点都有指向兄弟的指针

特点

节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少

总结各种数据结构

前面讲述了大量的数据结构，最后发现B树和B+树是较为合理的，可以作为索引底层的数据结构

评价数据结构是否适合作为索引的标准就是查询数据时磁盘IO的次数，因为磁盘IO的速度比起内存IO要慢上几个数量级

由于B树在非叶子节点同时存储数据和关键字，造成一个节点能够存储的数据个数不会太多，那么B树的高度就会比较高，磁盘IO的次数就会较多

B+树非叶子节点只存储关键字，因此能够存储的关键字更多，B+树的高度就不会太高，一般为3 ~ 4层。因此B+树的高度比B树低，磁盘IO次数更少

综上所述B+树更适合作为索引底层的数据结构

高维图结构

子主题

HNSW (Hierarchical Navigable Small World) 索引是一种高效的近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索算法，它主要用于大规模数据集中的高效查询。HNSW 索引的核心原理基于图论和小世界网络（Small World Network）的概念。

构建过程：

初始化：首先，对数据点进行排序，然后选择一个固定大小的邻居窗口，将每个数据点与其邻居连接起来，形成一个初始的邻接列表。
构建层次结构：递归地将这个邻接列表扩展为多层，每一层包含更远的邻居。相邻层之间的节点通过随机重采样连接，形成小世界结构。
添加新节点：当有新数据加入时，会根据其与现有节点的距离插入到适当的层次中，并调整邻接关系。
搜索过程：

查询：对于一个查询点，从根节点开始，沿着层次结构向下搜索，找到最接近的邻居节点。搜索过程中，如果遇到分支点，会优先考虑距离更近的分支。
扩散策略：为了提高搜索精度，HNSW 使用扩散策略，即从当前节点开始，不仅查看直接邻居，还会查看其邻居的邻居，直到达到预设的深度或找到足够数量的候选结果。
优点：

高效：HNSW 在处理大规模数据时非常高效，因为它使用了局部性原理，即相似的数据点在图中通常很接近。
可扩展性：可以动态添加和删除数据，而无需重建整个索引。
内存效率：由于采用了小世界结构，HNSW 可以在内存有限的情况下处理大量数据。
缺点：

精度与空间复杂度：随着图的层数增加，精度提高但空间复杂度也增大。需要权衡搜索精度和内存使用。
不适合高维数据：对于高维数据，HNSW 的性能可能会下降，因为高维空间中的“近似”可能不直观。

排序问题

冒泡排序

冒泡排序算法基础

算法原理

比较相邻元素

如果顺序错误则交换

逐轮减少比较范围

每轮确定一个最大值或最小值

时间复杂度分析

最坏情况时间复杂度

O(n^2)

平均情况时间复杂度