【数据】数据结构，数据查询，排序
2025-01-15 17:04:34 1 举报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)
优点：
高效：HNSW 在处理大规模数据时非常高效，因为它使用了局部性原理，即相似的数据点在图中通常很接近。
可扩展性：可以动态添加和删除数据，而无需重建整个索引。
内存效率：由于采用了小世界结构，HNSW 可以在内存有限的情况下处理大量数据。
缺点：
精度与空间复杂度：随着图的层数增加，精度提高但空间复杂度也增大。需要权衡搜索精度和内存使用。
不适合高维数据：对于高维数据，HNSW 的性能可能会下降，因为高维空间中的“近似”可能不直观。
HNSW (Hierarchical Navigable Small World) 索引是一种高效的近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索算法
它主要用于大规模数据集中的高效查询。HNSW 索引的核心原理基于图论和小世界网络（Small World Network）的概念。
构建过程：
初始化：首先，对数据点进行排序，然后选择一个固定大小的邻居窗口，将每个数据点与其邻居连接起来，形成一个初始的邻接列表。
构建层次结构：递归地将这个邻接列表扩展为多层，每一层包含更远的邻居。相邻层之间的节点通过随机重采样连接，形成小世界结构。
添加新节点：当有新数据加入时，会根据其与现有节点的距离插入到适当的层次中，并调整邻接关系。
构建层次结构：递归地将这个邻接列表扩展为多层，每一层包含更远的邻居。相邻层之间的节点通过随机重采样连接，形成小世界结构。
添加新节点：当有新数据加入时，会根据其与现有节点的距离插入到适当的层次中，并调整邻接关系。
搜索过程：
查询：对于一个查询点，从根节点开始，沿着层次结构向下搜索，找到最接近的邻居节点。搜索过程中，如果遇到分支点，会优先考虑距离更近的分支。
扩散策略：为了提高搜索精度，HNSW 使用扩散策略，即从当前节点开始，不仅查看直接邻居，还会查看其邻居的邻居，直到达到预设的深度或找到足够数量的候选结果。
优点：
高效：HNSW 在处理大规模数据时非常高效，因为它使用了局部性原理，即相似的数据点在图中通常很接近。
可扩展性：可以动态添加和删除数据，而无需重建整个索引。
内存效率：由于采用了小世界结构，HNSW 可以在内存有限的情况下处理大量数据。
缺点：
精度与空间复杂度：随着图的层数增加，精度提高但空间复杂度也增大。需要权衡搜索精度和内存使用。
不适合高维数据：对于高维数据，HNSW 的性能可能会下降，因为高维空间中的“近似”可能不直观。
排序问题
冒泡排序
冒泡排序算法基础
算法原理
比较相邻元素
如果顺序错误则交换
逐轮减少比较范围
每轮确定一个最大值
时间复杂度分析
最坏情况时间复杂度
O(n^2)
平均情况时间复杂度
O(n^2)
最好情况时间复杂度
O(n)
空间复杂度分析
辅助空间需求
常数级空间O(1)
原地排序特性
不需要额外数组
稳定性分析
相同元素相对位置不变
稳定排序算法
冒泡排序的实现
基本实现步骤
初始化变量
设置标志位
循环遍历数组
外层循环控制轮数
内层循环比较交换
相邻元素比较
代码示例
Python实现
def bubble_sort_recursion(self, array=None):
"""
# every loop block to find a max object by comparing one by one.
# then using recursion to sort remaining raw_array[0:n-1].
"""
n = len(array)
if n < 2:
return array
# using the for loop to find the max number index.
for i in range(0, len(array) - 1):
if array[i] > array[i + 1]:
temp = array[i]
array[i] = array[i + 1]
array[i + 1] = temp
return self.bubble_sort_recursion(array[0:n-1]) + [array[n-1]]
"""
# every loop block to find a max object by comparing one by one.
# then using recursion to sort remaining raw_array[0:n-1].
"""
n = len(array)
if n < 2:
return array
# using the for loop to find the max number index.
for i in range(0, len(array) - 1):
if array[i] > array[i + 1]:
temp = array[i]
array[i] = array[i + 1]
array[i + 1] = temp
return self.bubble_sort_recursion(array[0:n-1]) + [array[n-1]]
优化策略
标志位优化
提前结束排序
鸡尾酒排序（双向冒泡）
从两端向中间遍历
选择排序
选择排序算法
每次找到最小的元素
选择排序实现
代码示例
python实现
def selected_sort(self, array=None):
"""
# every loop block to find a min object, and then to exchange to the first position.
# opt: in one loop to find the min and max object at same time.
"""
if array:
self.raw_array = array
for j in range(0, len(self.raw_array) - 1): # n-1 times loop.
temp = self.raw_array[j]
for ii in range(j + 1, len(self.raw_array)):
if temp > self.raw_array[ii]:
temp = self.raw_array[ii]
self.raw_array[ii] = self.raw_array[j]
self.raw_array[j] = temp
return self.raw_array
"""
# every loop block to find a min object, and then to exchange to the first position.
# opt: in one loop to find the min and max object at same time.
"""
if array:
self.raw_array = array
for j in range(0, len(self.raw_array) - 1): # n-1 times loop.
temp = self.raw_array[j]
for ii in range(j + 1, len(self.raw_array)):
if temp > self.raw_array[ii]:
temp = self.raw_array[ii]
self.raw_array[ii] = self.raw_array[j]
self.raw_array[j] = temp
return self.raw_array
优化策略
同时找到最大最小
def selected_sort_opt(self, array=None):
"""
# every loop block to find a min index and max index,
# and then to exchange to the first and last position.
"""
if array:
self.raw_array = array
n = len(self.raw_array)
i_left = 0
i_right = n - 1
while i_left < i_right:
index_min, index_max = i_left, i_left
# find the min and max index in one loop from the left to right.
for i in range(i_left, i_right + 1):
if self.raw_array[index_min] > self.raw_array[i]:
index_min = i
if self.raw_array[index_max] < self.raw_array[i]:
index_max = i
# judge the min and max mun in one loop, and then to exchange the position.
if index_min != i_left:
tl = self.raw_array[i_left]
self.raw_array[i_left] = self.raw_array[index_min]
self.raw_array[index_min] = tl
if index_max == i_left:
index_max = index_min
if index_max != i_right:
tr = self.raw_array[i_right]
self.raw_array[i_right] = self.raw_array[index_max]
self.raw_array[index_max] = tr
i_left = i_left + 1
i_right = i_right - 1
return self.raw_array
"""
# every loop block to find a min index and max index,
# and then to exchange to the first and last position.
"""
if array:
self.raw_array = array
n = len(self.raw_array)
i_left = 0
i_right = n - 1
while i_left < i_right:
index_min, index_max = i_left, i_left
# find the min and max index in one loop from the left to right.
for i in range(i_left, i_right + 1):
if self.raw_array[index_min] > self.raw_array[i]:
index_min = i
if self.raw_array[index_max] < self.raw_array[i]:
index_max = i
# judge the min and max mun in one loop, and then to exchange the position.
if index_min != i_left:
tl = self.raw_array[i_left]
self.raw_array[i_left] = self.raw_array[index_min]
self.raw_array[index_min] = tl
if index_max == i_left:
index_max = index_min
if index_max != i_right:
tr = self.raw_array[i_right]
self.raw_array[i_right] = self.raw_array[index_max]
self.raw_array[index_max] = tr
i_left = i_left + 1
i_right = i_right - 1
return self.raw_array
快速排序
快速排序算法
通过标点元素pivot和2个分大小list完成自迭代
一次迭代把元素分到不同的list里
快速排序算法实现
代码案例
python实现
def quick_sort(self, array=None):
"""
# using the first element to be the pivot.
# using the left and right pointer to compare the element.
# opt: using the random element to be the pivot.
"""
if array is None:
array = self.raw_array
n = len(array)
if n < 2:
return array
# using the first element to be the pivot.
pivot = array[0]
left = list()
right = list()
for i in range(1, n):
if array[i] < pivot:
left.append(array[i])
else:
right.append(array[i])
# using recursion to sort the left and right array.
left = self.quick_sort(array=left)
right = self.quick_sort(array=right)
return left + [pivot] + right
"""
# using the first element to be the pivot.
# using the left and right pointer to compare the element.
# opt: using the random element to be the pivot.
"""
if array is None:
array = self.raw_array
n = len(array)
if n < 2:
return array
# using the first element to be the pivot.
pivot = array[0]
left = list()
right = list()
for i in range(1, n):
if array[i] < pivot:
left.append(array[i])
else:
right.append(array[i])
# using recursion to sort the left and right array.
left = self.quick_sort(array=left)
right = self.quick_sort(array=right)
return left + [pivot] + right
优化策略
随机选取标杆point
def quick_sort_opt(self, array=None):
"""
# using the random element to be the pivot.
# using the left and right pointer to compare the element.
"""
if array is None:
array = self.raw_array
n = len(array)
if n < 2:
return array
# using the random element to be the pivot.
pivot = array[random.randint(0, n - 1)]
left = list()
right = list()
for i in range(0, n):
if array[i] < pivot:
left.append(array[i])
else:
right.append(array[i])
# using recursion to sort the left and right array.
left = self.quick_sort(array=left)
right = self.quick_sort(array=right)
return left + right
"""
# using the random element to be the pivot.
# using the left and right pointer to compare the element.
"""
if array is None:
array = self.raw_array
n = len(array)
if n < 2:
return array
# using the random element to be the pivot.
pivot = array[random.randint(0, n - 1)]
left = list()
right = list()
for i in range(0, n):
if array[i] < pivot:
left.append(array[i])
else:
right.append(array[i])
# using recursion to sort the left and right array.
left = self.quick_sort(array=left)
right = self.quick_sort(array=right)
return left + right
希尔排序
堆排序
检索问题
顺序查找
二分法查找
聊聊精排
“精排”或精细化排序，在数据库查询和搜索场景下，通常表示对搜索结果的一种高级筛选和排序策略
条件限制
权重计算（依据用户喜好、评分等因素）
更加复杂的算法以提供满足用户特定偏好结果的排序方式，动态调整结果权重、相关度排名等。
“索引能力”在此过程中至关重要，因为良好的索引能够显著提高查找的速度，减少搜索结果的计算成本
使用适当的索引能提升“最近用户评价”“按价格区间过滤产品”或是类似基于某种属性或关系的快速过滤需求
添加额外的索引以跟踪和聚合用户行为，可以在推荐系统或个性化服务上发挥巨大作用，实现精确用户偏好和内容推荐
0 条评论
下一页
