企业官网建设流程全解析

有没有手机可以看的网站免费的,网站群项目建设实施进度计划,怎样网站建设与管理,html5网页开发工具数据结构#xff1a;DBMS在系统内部的许多不同部分使用各种数据结构#xff0c;一些例子包括#xff1a;内部元数据 (Internal Meta-Data)#xff1a;用于跟踪关于数据库和系统状态信息的数据。例如#xff1a;页表 (Page tables)、页目录 (Page directories)。核心数据存…数据结构DBMS在系统内部的许多不同部分使用各种数据结构一些例子包括内部元数据 (Internal Meta-Data)用于跟踪关于数据库和系统状态信息的数据。例如页表 (Page tables)、页目录 (Page directories)。核心数据存储 (Core Data Storage)作为数据库中元组 (Tuples) 基础存储的数据结构。临时数据结构 (Temporary Data Structures)DBMS 可以在处理查询时动态构建临时的 ephemeral 数据结构以加速执行。例如用于连接操作 (Joins) 的哈希表。表索引 (Table Indices)用于更轻松地查找特定元组的辅助数据结构。核心设计决策在为DBMS实现数据结构时主要有两个设计决策需要考虑数据组织 (Data Organization)我们需要弄清楚如何布局内存以及在数据结构内部存储什么信息以支持高效访问。并发性 (Concurrency)我们还需要考虑如何允许多线程同时访问数据结构而不引发问题确保数据保持正确和稳健。哈希表哈希表实现了一种将键映射到值得关联数组抽象数据类型。复杂度它提供平均 O(1) 的操作复杂度最坏情况下为 O(n)和 O(n) 的存储复杂度。注意即使平均操作复杂度是 O(1)在现实世界中常数因子优化也是非常重要的考量因素比如一次计算哈希耗时 1ns 还是 100ns。一个哈希表得实现由两部分组成1.哈希函数它告诉我们如何将一个巨大的键空间映射到一个较小的目标域中用于计算桶或槽数组的索引。我们需要在执行速度和冲突率之间权衡极端情况 A一个总是返回常数的哈希函数计算非常快但所有数据都会发生冲突退化成链表。极端情况 B一个“完美”的哈希函数完全没有冲突但计算起来可能需要极长的时间。理想设计介于这两者之间。2.哈希方案它告诉我们哈希计算如何处理键的冲突。在这里我们需要权衡是分配一个巨大的哈希表来减少冲突发生的概率还是节省空间但在冲突发生时不得不执行额外的指令来寻找空位。哈希函数哈希函数接受任何键作为输入并返回该键的整数表示即哈希值。该函数的输出具有确定性——即相同的键必须始终产生相同的哈希输出。DBMS不需要使用加密级安全的哈希函数因为我们不需要担心保护键的内容。这些哈希函数主要由DBMS内部使用因此信息不会泄漏到系统外部。通常情况下我们只关心哈希函数的执行速度和冲突率。目前最先进的哈希函数是Facebook的XXHash3.线性探测哈希这是最基础也是通常最快的哈希方案它使用一个数组槽位的循环缓冲区。基本原理哈希函数将键映射到槽位。插入发生冲突时线性地搜索相邻槽位直到找到空位。查找检查键哈希到的槽位并线性搜索直到找到目标条目。如果遇到空槽位或遍历了表中所有槽位说明键不存在。存储内容槽位必须同时存储 键 (Key) 和 值 (Value)以便验证条目是否为所需目标。删除操作直接移除条目非常危险因为这可能导致后续查找无法找到原本排在空槽位之后的条目。有两种解决方法墓碑 (Tombstones)最常用用“墓碑”标记被删除的槽位告诉后续查找操作继续扫描而非停止。数据移动删除后移动相邻数据填补空位但必须小心只移动那些本就被偏移过的条目。这在实践中很少见因为当键数量巨大时开销极高。非唯一键 (Non-unique Keys)当一个键关联多个值时独立链表存储指向包含所有值链表的指针。冗余键更常用直接在表中多次存储相同的键。优化手段专用化实现根据键的类型如长短字符串采取不同的存储策略。独立存储元数据使用位图 (Bitmap) 记录空位/墓碑信息避免无效查找。版本控制通过增加版本计数器来批量作废槽位避免昂贵的逐个清理操作。布谷鸟哈希这种方法不只使用一个哈希表而是维护多个具有不同哈希函数通常算法相同但种子不同如不同种子的 XXHash的哈希表。插入逻辑检查所有表选择有空位的表进行插入。如果没有空位随机选择一个表并驱逐 (Evict) 其中的旧条目。将被驱逐的旧条目重新哈希到另一个表中。如果陷入无限循环则重建所有表更换种子或增大容量后者更常见。性能特点查找与删除保证 O(1) 复杂度。插入开销可能更高因为涉及链式驱逐。在实践中布谷鸟哈希通常是在单个哈希表上使用多个哈希函数将键映射到不同槽位此外由于哈希计算本身有开销其查找和删除的成本实际上可能略高于理想的O(1)。虽然布谷鸟哈希在理论上提供了“最坏情况下 O(1)”的查找但在现代计算机架构下线性探测通常表现更好缓存局部性 (Cache Locality)线性探测是连续访问内存这非常符合 CPU 的缓存预取逻辑。而布谷鸟哈希需要计算多个哈希并在不同的内存位置跳转容易产生 Cache Miss。简单即美线性探测的代码逻辑非常精简分支预测更容易命中。动态哈希方案静态哈希方案要求DBMS预先知道其想要存储的元素数量。否则如果哈希表需要扩大或缩小容量就必须进行重建。动态哈希方案能够根据需求调整哈希表的大小而无需重建整个表。这些方案通过不同的方式执行容量调整可以分别侧重于优化读取或写入性能。链式哈希这是最常见的动态哈希方案。DBMS 为哈希表中的每个槽位维护一个由“桶Buckets”组成的链表。哈希到同一个槽位的键会被简单地插入到该槽位对应的链表中。查找元素时我们通过哈希定位到对应的桶然后进行扫描。这种方案可以通过在桶指针列表中额外存储 布隆过滤器来优化它可以告知我们某个键是否不存在于链表中从而在这些情况下避免查找操作。可扩展哈希这是链式哈希的一种改进变体它通过拆分桶来代替让链表无限制增长。这种方案允许哈希表中的多个槽位指向同一个桶链。重平衡哈希表的核心思想是在拆分时移动桶内条目并增加用于查找哈希表中条目的位数。这意味着 DBMS 只需在被拆分链的桶内移动数据所有其他桶都保持不变。DBMS 维护 全局深度和 局部深度位数用于确定在槽数组中寻找桶所需的位数。全局深度是整个目录的同一深度它决定了用于查找哈希表中条目的位数也就是用多大的精度来解析哈希值。局部深度是桶内的值的数量。当一个桶满时DBMS 拆分该桶并重新排列其元素。如果被拆分桶的局部深度小于全局深度则只需将新桶添加到现有的槽数组中。否则DBMS 将槽数组的大小翻倍以容纳新桶并增加全局深度计数器。此时由于多个槽位可能指向同一桶必须进行分裂。可扩展哈希的意义是防止局部深度像链式哈希那样无限制的扩张。线性哈希在链式哈希中如果某个桶溢出了你只能在后面挂桶结构被动地变得越来越深。该方案不是在桶溢出时立即进行拆分而是维护一个 拆分指针 (Split Pointer)用于跟踪下一个要拆分的桶。无论该指针是否指向溢出的那个桶DBMS 都会执行拆分。溢出的判定标准由具体实现决定。当任何桶发生溢出时拆分指针当前位置的桶。添加一个新的槽条目和一种新的哈希函数并应用此函数对拆分桶中的键进行重哈希。如果原始哈希函数映射到了拆分指针之前指向过的槽位则应用新的哈希函数来确定键的实际位置。当指针到达最后一个槽位时删除原始哈希函数并将指针移回开头。如果拆分指针下方的最高位桶为空我们也可以移除该桶并反向移动拆分指针从而缩小哈希表的大小。线性哈希好处在于平滑扩容整个哈希表利用率维持在一个相对稳定的空间且比可扩展哈希更省内存。