二分法查找 二分法查找也称为折半查找，用于在一个有序数组中快速定义某一个需要查找的数据。...2、左子树和右子树是有顺序的，次序不能任意颠倒，左子树的值要小于父结点，右子树的值要大于父结点。 数组[20,10,5,15,30,25,35]使用二叉查找树存储如下： ?...表中的数据发生变更的时候，会影响其他记录地址的变化，如果辅助索引中记录数据的地址，此时会受影响，而主键的值一般是很少更新的，当页中的记录发生地址变更的时候，对辅助索引是没有影响的。...的取值范围为[1,8]，其他用户记录n_owned的取值范围[4,8]，并且只有每个块中最大的那条记录的n_owned才会有值，其他的用户记录的n_owned为0。...本篇到此，下一篇实战篇对mysql索引使用上面做详细介绍
，此时数组中已经有其他元素占了这个下标位置，这种存储位置重复了的情况便叫做 冲突，我们来看个例子： 使用链表解决冲突问题 遇到存储冲突问题时，可使用 链表[1] 在已有数据的后面继续存储新的数据，也称之为链地址法...例如要查询Dan的值 对Dan进行mod运算得出值为4，则得之Dan在数组的下标是4 取出Dan对应的value值为M 数组中的链表数据查询 将需要查找的key进行mod运算，得到结果后，发现对应下标下的...例如，需要查询Ally键对应的value值： 求出Ally的哈希值，对哈希值进行mod运算，得出值为3： 对下标为3元素的连败哦进行线性查找，找到Ally元素： 哈希表的优点 在哈希表中，可以利用哈希函数快速访问到数组中的目标元素...堆的特点 如下图所示，每个节点由两个子节点，用线条连接即为堆： 结点内的数字就是存储的数据 堆中的每个结点最多有两个子节点 树的形状取决于数据的个数 节点的排列顺序为从上到下，同一行里则为从左到右 堆的父节点必须小于子结点...如图所示，即为一个二叉查找树的示例： 二叉查找树的特点 同堆一样，每个节点最多有两个子结点 每个结点的值均大于其左子树上任意一个结点的值 每个结点的值均小于其右子树上任意一个结点的值 查询二叉树中最小值要从顶端开始找他的左子树
哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。 不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。...所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。 有序数组 有序数组在等值查询和范围查询场景中的性能就都非常优秀。...这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。...每个节点最多有m-1个关键字（可以存有的键值对）。 根节点最少可以只有1个关键字。 非根节点至少有m/2个关键字。...每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。...所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。 有序数组在等值查询和范围查询场景中的性能就都非常优秀。...4.1 B-Tree image.png m阶B树定义 根节点至少包括两个孩子 树中每个节点最多含有m个孩子（m>=2）(m个孩子就称之为m阶树) 关键字个数最多为m-1个(根据孩子结点来的,比孩子结点少一个...) 除根节点和叶节点外，其他每个节点至少有ceil（m/2）个孩子 所有叶子节点都位于同一层 4.2为什么用B-树可以很矮,很胖，速度很快呢?...应尽量避免在where子句中对 字段进行函数操作或者表达式操作，这将导致引擎放弃使用索引而进行全表扫描。
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。 二分法的有点事查找速度快，但是仅当列表是有序的时候，二分查找才管用。 ...因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。 一些常见的大O运行时间 O(log n)，也叫对数时间，这样的算法包括二分查找。 ...首先，从数组中选择一个元素，这个元素被称为基准值； 接下来，找出比基准值小的元素以及比基准值大的元素。 再对这两个子数组进行快速排序，直到满足基线条件。...第一行是吉他行，你只能选择拿不拿吉他，只能拿其他肯定会拿偷啊，这样利益最大化。 第二行是音箱行，你可以选择吉他或音箱。 第三行电脑行，三种都可以选择。 ...这里行排列的顺序变化了对结果没什么影响。并且最优解可能背包还没装满。 但仅当 每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
（基于链表实现，继承链表特征） 使用特点：先进先出，后进后出 树 结构特征：每个节点有0个或多个子节点 二叉树 结构特征：每个节点最多有两个子节点 二叉查找树 结构特征：每个节点最多有两个节点...，且左子树的值值值 使用特点：二叉查找树的查询，插入的时间复杂度都为O(logn) 平衡二叉树 结构特征：在二叉查找树的基础上，加了限制条件：每个节点的左子树和右子树高度差最多为...结构特征：只在叶子节点存储数据，且叶子节点有序排列，通过链指针相连（只有叶子节点保存数据，其他节点都只保存索引，单次IO能加载更多节点） 使用用法：B树解决了磁盘IO问题，而B+树通过数据结构优化和区间访问加快了元素的查找效率...：将元素按块有序划分，块内无序，块与块之间有序，比如说第一个块的任意一个元素小于第二个块中的任意一个元素 流程：先取出每个块中的最大值构成索引表，然后使用顺序查找或二分查找确定块，然后顺序查找当前块...时间复杂度：O(logn) 哈希查找 典型实现：HashMap，使用数组+链表的结构 时间复杂度：在不形成链表的情况下时间复杂度为O(1)，反之时间复杂度为O(n)，1.8中引入红黑树，时间复杂度为
3.1.4 时间复杂度 二叉搜索树查找数据的时间复杂度是O(logN)，如图所示，最多查找3次就可以查到所需数据。...3.5 hash 3.5.1 hash冲突 将车库中的车牌号按简称排列，重复的简称，可成为hash冲突。 多个不同的值通过算出了同一个hash值被称之为hash冲突。...2、Hash 索引不支持联合索引的最左侧原则 对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。...在 update 语句的 where 条件没有使用索引，就会全表扫描。 使用索引后，使用“行锁”进行udpate，只锁当前行。...不影响其他行的查询更新 3.2 不当索引导致性能开销 使用性别等字段，导致数据查询效果性能提升不大，且增加修改成本。
台机器，平均分布在16个不同的地点，试给每一地点分配一个子网号码，要求能分配的子网数最多的情况下，每个子网里面的主机数也能容纳一个地点的所有主机，则子网掩码选择为多少，这种情况下可以划分多少个子网？...如果是在空间复杂度最优为___的情况下，时间复杂度最优为___？ 在空间复杂度最优的情况下，可以使用数组本身来记录 M 中每个数是否出现过。...某操作系统中，页面大小为4k，分配给每个进程的物理页面数为1。在一个进程中，定义了如下二位数组int A[512][512]，该数组按行存放在内存中，每个元素占8个字节。...std::function func;其中A表示接受函数的返回值，B表示参数，那么依次推测如下代码中哪几行添加是对的?...1、2、4 行是对的，可以添加到 vector 中。
在算法中使用数组 在算法中，数组通常用于优化算法和提高性能。例如，我们可以使用一个数组来记录某个数出现的次数，然后快速找到出现次数最多的数。 ...最后，我们使用另一个循环代码分析： 这个方法接收一个整型数组作为参数，然后返回该数组中出现次数最多的元素。 方法首先创建一个 HashMap，并迭代元素数组中的每个元素，对每个元素进行计数。...在算法中使用数组 在算法中，数组通常用于优化算法和提高性能。例如，我们可以使用一个数组来记录某个数出现的次数，然后快速找到出现次数最多的数。...它包含了一个静态方法 findMostFrequentElement，用于查找给定数组中出现次数最多的元素。在该方法中，首先创建了一个名为 count 的 HashMap，用于存储每个元素出现的次数。...接下来，使用循环遍历 count 中的所有元素，并找出出现次数最多的元素，并将其值赋给了 mostFrequentElement 变量。最后，该方法返回了出现次数最多的元素。
索引的出现其实是为了提高数据查询的效率，就像书的目录一样，根据目录可以快速定位到内容，类比于索引，根据索引提供指向存储在表的指定列中的数据值的指针，根据指针找到包含该值的行。...索引的常见模型 哈希表 有序数组 B+树 哈希表 哈希表模型是将待查询的值放入key中，value值放入数组中， 图片 当使用哈希表时，key值计算成确定位置，将value值放入该地址对应的哈希槽，取值通过...有序数组 有序数组在等值查询和范围查询场景中的性能都非常优秀。 仅看查询效率，有序数组是最好的数据结构，使用二分法查询可以快速查询到目标值，时间复杂度是O(log(N))。...图片 O(log(N))：使用二分法查询，最理想的情况是查询一次即可，最坏的情况下需要查询的次数。 16个元素的有序数组，使用二分法查找其中一个元素，最多需要查询log 2 16 = 4次。...树高是4的时候，就可以存1200的3次方个值（17亿），树根的数据总是存在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。
但是如果需要经常做某一个操作，则类似的代码需要重复写很多遍，比如在一个数组中查找某个数，第一次查找一个数，第二次可能查找另一个数，每查一个数，类似的代码都需要重写一遍，很罗嗦。...函数可以调用同一个类中的其他函数，也可以调用其他类中的函数，我们在前面几节使用过输出一个整数的二进制表示的函数，toBinaryString： int a = 23; System.out.println...函数返回值类型为void也可以使用return，即return;，不用带值，含义是返回调用方，只是没有返回值而已。 返回值的个数 函数的返回值最多只能有一个，那如果实际情况需要多个返回值呢？...我想说的是，虽然返回值最多只能有一个，但其实一个也够了。 函数命名 每个函数都有一个名字，这个名字表示这个函数的意义，名字可以重复吗？在不同的类里，答案是肯定的，在同一个类里，要看情况。...同一个类里，函数可以重名，但是参数不能一样，一样是指参数个数相同，每个位置的参数类型也一样，但参数的名字不算，返回值类型也不算。
图1 字谜单词字符排列示意图 现在至少也有两种直观的算法来求解这个问题： 对单词表中的每个单词，检查每一个有序三元组（行，列，方向）验证是否有单词存在。...对于每一个尚未越出迷板边缘的有序四元组（行，列，方向，字符数）可以测试是否所指的单词在单词表中。这也导致使用大量嵌套的for循环。...0； 当某个key加入的时候，用k个hash函数计算出k个散列值，并把数组中对应的比特置为1； 判断某个key是否在集合时，用k个hash函数算出k个值，并查询数组中对应的比特位，如果所有的bit位都为...· 数据结构和算法 AVL树本质上还是一棵二叉查找树，有以下特点： AVL首先是一棵二叉搜索树； 带有平衡条件：每个节点的左右子树的高度之差的绝对值最多为1； 当插入节点或者删除节点时，树的结构发生变化导致破坏特点二时...· 数据结构和算法 首先，先了解一下一棵m阶B-Tree的特性： 每个节点最多有m个子节点； 除了根节点和叶子结点外，其他每个节点至少有m/2个子节点； 若根节点不是叶子节点，则至少有两个子节点； 所有的叶子结点都是同一深度
，通过一个整数也就是下标值，在一个数组里面有且仅有一个唯一的值与之对应，有点类似于经过去重的数组一样，但是这种映射是有规律可循的。...链地址法：每个数组元素不直接存储键值对，而是存储一个链表。当多个键通过哈希函数映射到同一索引时，这些键值对将被存储在同一个链表中。 2....开放寻址法：当发生哈希碰撞时，哈希映射会尝试找到数组中的下一个空闲位置，按照某种系统的方式（如线性探测）进行。...map 在使用map时，需要加入头文件#include，下面解析一下map常用的函数: 1.insert insert是插入函数，在指定的下标位置插入键值映射。...输入格式 第一行一个整数n表示点的个数 以下n行，每行2个整数分别表示每个点的x,y坐标。 输出格式 输出一个整数表示答案。
在查找时，对给定关键字通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。...这指的是在并发环境中，当不同的事务同时操纵相同的数据时，每个事务都有各自的完整数据空间。由并发事务所做的修改必须与任何其他并发事务所做的修改隔离。...在聚簇索引下，数据在物理上按顺序排在数据页上，重复值也排在一起，因而在那些包含范围检查(between、、>=)或使用group by或orderby的查询时，一旦找到具有范围中第一个键值的行...该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访 问。...主键索引不仅仅具有索引的特征，还包含着主键约束，如不为空，值唯一的特征 主键可以被其他表引用为外键，而唯一索引不能 一个表最多只能创建一个主键，但可以创建多个唯一索引 11.
查找表:在计算机中，是指被查找的数据对象是由同一个类型的记录构成的集合，如顺序表、链表、二叉树和哈希表等。...查找操作及分类 操作： 查找某个“特定的”数据元素是否成存在在查找表里。 某个“特定的”数据元素的各种属性。 在查找表中插入一个数据元素。 从查找表中删除某个数据元素。...数组和索引 索引把线性表分为若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按关键字大小顺序排列。即前一块中的最大关键字值小于后一块中的最小关键字值。...直接对四种类型的硬币的个数进行穷举。其中，1 元最多 10 枚、5 角最多 20 枚、1 角最多 20 枚、5 分最多 20 枚。...进程： 通常每个进程对应一个在运行中的执行程序，比如，QQ 和微信运行的时候，他们分别是不同的进程。 任一时刻，单个 CPU 一次只能运行一个进程，此时其他进程处于非运行状态。
HashSet中的每个元素都存储为HashMap中的一个键（key），而对应的值（value）则是一个固定的对象（在Java 8及更高版本中，这个对象是一个名为PRESENT的静态常量，而在Java 7...在 HashSet 中，每个元素实际上都作为 HashMap 的一个键（key）存储，而对应的值（value）则是一个固定的对象（在 Java 8 及以后版本中，这个固定对象是一个 PRESENT 常量...HashSet（通过其内部的 HashMap）使用链表或红黑树（在 Java 8 及更高版本中，当链表长度超过一定阈值时，链表会转换为红黑树以提高查找效率）来解决哈希冲突。...允许使用null元素。 HashMap： 键（Key）是唯一的，值（Value）可以重复。 允许使用null键和null值（但最多只能有一个null键）。 提供了基于键的快速查找、插入和删除操作。...HashMap：同样使用哈希表来存储键值对。每个键值对都通过哈希函数计算出一个哈希码，然后根据这个哈希码将键值对存储在数组的某个位置。
如何在一维存储器中存放二维数组，可有两种方式：一种是按行排列， 即放完一行之后顺次放入第二行。另一种是按列排列， 即放完一列之后再顺次放入第二列。在C语言中，二维数组是按行排列的。...，按照键值对的方式存储，其中文名字翻译为字典，顾名思义其通过键名查找对应的值会有很高的效率，时间复杂度在常数级别O(1) dict底层实现 在Python中，字典是通过 哈希表 实现的。...链地址法 将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到。...3.如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决冲突。 在使用拉链法解决哈希冲突时，每个箱子其实是一个链表，属于同一个箱子的所有键值对都会排列在链表中。...所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。 ? 二叉树 在计算机科学中，二叉树是每个结点最多有两个子树的树结构。
B-Tree不同于Binary Tree（二叉树，最多有两个子树），一棵M阶的B-Tree满足以下条件： 1）每个结点至多有M个孩子； 2）除根结点和叶结点外，其它每个结点至少有M/2个孩子； 3）根结点至少有两个孩子...对于每个结点，主要包含一个关键字数组Key[]，一个指针数组（指向儿子）Son[]。...在B-Tree内，查找的流程是：使用顺序查找（数组长度较短时）或折半查找方法查找Key[]数组，若找到关键字K，则返回该结点的地址及K在Key[]中的位置；否则，可确定K在某个Key[i]和Key[i+...在高层的索引页中包含RowId是为了当索引允许重复值时，当更改数据时精确定位数据行。 C）下一级索引页的指针 对于叶子层的索引对象，它的结构包括： A）索引字段值 B）RowId ?...由于非聚集索引的叶结点包含所有数据行中的索引列值，使用这些结点即可返回真正的数据，这种情况称之为“索引覆盖”。
面试题1：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？...IP地址是字符串太长，我们可以把它转化为整型%100，这样取模后的值都落在0-99的区间里，所取模后值相同的IP地址都被分配到同一个文件，这时我们就可以采用哈希表统计出每个文件中最多的那个IP地址，最后比较得到...还遇到一个问题，就是到底怎么定义这个数组，正数好定义，负数的话我们可以用32位全1（-1）和它取异或取到和正数相同的位置，我们此时定义一个二维数组，一半表示正数一半表示负数，都位于同一行。...，这样我们只要比较取模的为同一值的两个文件比较就可以了，如果相同则标记。...使用BloomFilter可以进行判断元素在集合的存在与否。
数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样 每个节点只需要一次I/O 就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构， h 明显要深的多。...在哈系索引的中查询一个像“Jesus”这样的值，并得到对应行的在内存中的引用，明显要比扫描全表获得值为“Jesus”的行的方式快很多。...指针是指一块内存区域， 该内存区域记录的是对硬盘上记录的相应行的数据的引用。因此，索引中除了存储列的值，还存储着一个指向在行数据的索引。...同样的，就像一本书的索引包含页码一样，数据库的索引包含了指针，指向你在SQL中想要查询的值所在的行。 使用数据库索引会有什么代价？ 那么，使用数据库索引有什么缺点呢？ ...位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
腾讯会议
对象存储
云直播
