当前位置: 首页 > news >正文

a网站建设/市场调研方法有哪些

a网站建设,市场调研方法有哪些,公司做网络推广哪个网站好,wordpress英文版中文版目录 一、基本介绍 二、重要概念 非叶节点 叶节点 三、阶数 四、基本操作 等值查询(query) 范围查询(rangeQuery) 更新(update) 插入(insert) 删除(remove) 五、知识小结 一、基本介绍 B树是一种树数据结构,通常用于数据库和操作系统的文件系统中。 B树…

目录

一、基本介绍

二、重要概念

非叶节点

叶节点

三、阶数

四、基本操作

等值查询(query)

范围查询(rangeQuery)

更新(update)

插入(insert)

删除(remove)

五、知识小结


一、基本介绍

B+树是一种树数据结构,通常用于数据库和操作系统的文件系统中。

B+树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。

B+树被用于MySQL数据库的索引结构。这里为了便于大家理解,我基于内存(因为数据量的原

因,实际上的B+树应该基于磁盘等外存,基于内存的比较适合作为Demo,同时还可以作为一种多

路搜索树)实现了B+树的增删查改操作(包括节点分裂和节点合并)

二、重要概念

B+ 树是一种树数据结构(一个n叉树),这里我们首先介绍B+树最重要的概念:B+树节点。

一棵B+树的节点包含非叶节点叶子节点两类

非叶节点

如上图所示,非叶节点包含两部分信息

  • Entry: 索引键,用于索引数据,它必须是可比较的,在查找时其实也是根据Entry的有序性来加快查找速度(原理和二分查找类似,通过有序性来剪枝搜索空间,所以是对数级的实际复杂度)
  • Child: 指向其孩子节点的指针,可以通过它访问到该非叶节点的子节点

对于非叶节点来说,Child孩子指针的数量总是等于Entry的数量加1,也就是说一个非叶节点如果

有3个Entry的话,那么就可以得到它有 3+1=4 个孩子(子节点)。

叶节点

如上图所示,叶节点包含三部分信息:

  • Entry: 与非叶节点中的Entry一致,用于索引数据
  • Data指针: 用于指向具体数据的指针(从这里可以发现,非叶节点的指针只能找到它的孩子的地址,而真正的数据的地址只能通过叶节点找到,即可以理解为所有数据都存储在叶节点上)
  • Next指针: 用于指向该叶节点的后面一个叶子节点,最后一个叶子节点的Next指针为空(Next指针存在的意义是加快范围查询)。

对于叶节点来说,Data数据指针的数量总是等于Entry的数量,也就是说一个叶节点如果有3个

Entry的话,那么就可以得到它索引了3个数据项,这里与非叶节点不同的原因是叶节点分出了一个

指针去指向了下一个叶节点,所以其实无论是非叶节点还是叶节点,他们Entry数量和指针数量的

关系都是:指针数量等于Entry数量加1。

为了使逻辑更加清晰,后面我在介绍”B+树的操作“时将会按非叶节点和叶节点分别进行讨论。

三、阶数

一棵B+树通常用 m 来描述它的阶数,它的作用是描述一个B+树节点中Entry数量的上限和下限。

在大多数对于B+树的介绍了,一般描述一个m阶的B树具有如下几个特征

  1. 根结点至少有两个子女。
  2. 每个中间节点都至少包含ceil(m / 2)个孩子,最多有m个孩子。
  3. 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m。
  4. 所有的叶子结点都位于同一层。
  5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划

上面的特征可能看起来会比较复杂,所以这里用我自己的一个更简单的理解来解释一下。

我们设一个B+树节点的Entry数量上限为Key_Bound,简写为K,则 K = m - 1。得到K之后,获取

Entry数量的下限也变得很简单,就是 K / 2 (整型除法,下取整)

根据我们上面对B+树节点的介绍,我们可以根据K得到很轻松地得到节点中对应指针的数量: K +

1

用代码表示如下:

public BPlusTree(int order) {this.KEY_UPPER_BOUND = order - 1; //Entry 上限this.UNDERFLOW_BOUND = KEY_UPPER_BOUND / 2; //Entry 下限
}

这样我们拿到了B+树中Entry的上限、下限及对应的指针数量之后,后面我们就可以不必再理会那

个计算更复杂的m了。

在实际的应用中,B+树的阶数其实越大越好,因为当B+树的阶数越大,B+树一个节点所能容纳的

Entry就会越多,B+树就会变得更”矮“,而更”矮“意味着更少的磁盘I/O,所以一般情况下B+树的阶

数跟磁盘块的大小有关。

四、基本操作

等值查询(query)

B+树的等值查询指:找到B+树叶节点Entry与查询Entry完全相等所对应的数据,等值查询的过程

主要是依赖于Entry的有序性:设B+树某个节点的Entry e 是第index个Entry,则该节点的第index

个孩子中的所有Entry都是小于e的,该节点的第index+1个孩子中的所有Entry都是大于等于e的。

所以我们可以根据这个有序性,自顶向下逐层查找,最终找到匹配的叶子节点然后获取到数据。

对于非叶节点,只需要找到第一个大于查询Entry的子节点,即 upper bound(如果所有子节点都

小于等于查询Entry,则 uppber bound 为子节点的数量),然后如此递归地让这个子节点进行查找

即可。

其中最关键的就是找到第一个大于查询Entry的子节点 upper bound,因为查询Entry只可能出现在

upper bound 的前一个位置。由于B+树Entry的有序性,在这里我们可以使用二分搜索实现这一

点,因为二分搜索的效率非常高(O(logN)级别),代码实现如下:

        protected int entryIndexUpperBound(K entry) {int l = 0;int r = entries.size();while (l < r) {int mid = l + ((r - l) >> 1);if (entries.get(mid).compareTo(entry) <= 0) {l = mid + 1;} else {r = mid;}}return l;}

找到这个子节点之后,让它继续查找即可:

        @Overridepublic List<E> query(K entry) {return children.get(findChildIndex(findEntryIndex(entry), entry)).query(entry);}

对于叶节点,就需要找到与查询Entry完全相等的Entry:

        @Overridepublic List<E> query(K entry) {int entryIndex = getEqualEntryIndex(entry);return entryIndex == -1 ? Collections.emptyList() : new ArrayList<>(data.get(entryIndex));}

如果没有与查询Entry相等的Entry,则返回空集,否则返回对应的数据。

同样地,在找与查询Entry相等的Entry,为了提高效率我们也可以使用二分搜索:

        private int getEqualEntryIndex(K entry) {int l = 0;int r = entries.size() - 1;while (l <= r) {int mid = l + ((r - l) >> 1);int compare = entries.get(mid).compareTo(entry);if (compare == 0) {return mid;} else if (compare > 0) {r = mid - 1;} else {l = mid + 1;}}return -1;}

下面是B+树等值查询的一个例子:

bPlusTree.insert(0, "data record 1");
bPlusTree.insert(0, "data record 2");
bPlusTree.insert(1, "data record 3");
bPlusTree.insert(2, "data record 4");
bPlusTree.insert(3, "data record 5");//query all data records under the entry 0
List<String> queryResult = bPlusTree.query(0);
System.out.println(queryResult); //[data record 2, data record 1]

范围查询(rangeQuery)

B+树的范围查询指:给定查询上限Entry K1,查询下限Entry K2, 找到B+树叶节点Entry满足在

[K1, k2) 范围内。

对于非叶节点来说,查询过程与等值查询过程完全一致:

        @Overridepublic List<E> rangeQuery(K startInclude, K endExclude) {return               children.get(findChildIndex(findEntryIndex(startInclude),startInclude)).rangeQuery(startInclude, endExclude);}

对于叶节点来说,将等值查找改为范围查找即可:

        @Overridepublic List<E> rangeQuery(K startInclude, K endExclude) {List<E> res = new ArrayList<>();int start = findEntryIndex(startInclude);int end = findEntryIndex(endExclude);for (int i = start; i < end; ++i) {res.addAll(data.get(i));}BPlusTreeLeafNode nextLeafNode = next;while (nextLeafNode != null) {for (int i = 0; i < nextLeafNode.entries.size(); ++i) {if (nextLeafNode.entries.get(i).compareTo(endExclude) < 0) {res.addAll(nextLeafNode.data.get(i));} else {return res;}}nextLeafNode = nextLeafNode.next;}return res;}

在进行范围查询时,我们利用next指针直接获取到了下一个叶子节点,

而不是从根节点从上到下又搜索一遍,以此提高了范围查找的效率。

下面是B+树范围查询的一个例子:

//query all data records under the entries [0,3)
List<String> queryResult = bPlusTree.rangeQuery(0, 3);
System.out.println(queryResult); //[data record 2, data record 1, data record 3, data record 4]

更新(update)

B+树的更新操作比较简单,即通过查询找到对应的数据之后将旧值更新为新值即可。

非叶节点的更新操作过程:

        @Overridepublic boolean update(K entry, E oldValue, E newValue) {return children.get(findChildIndex(findEntryIndex(entry), entry)).update(entry, oldValue, newValue);}

叶节点的更新操作过程:

        @Overridepublic boolean update(K entry, E oldValue, E newValue) {int entryIndex = getEqualEntryIndex(entry);if (entryIndex == -1 || !data.get(entryIndex).contains(oldValue)) {return false;}data.get(entryIndex).remove(oldValue);data.get(entryIndex).add(newValue);return true;}

插入(insert)

B+树的插入操作相对于查询操作和更新操作来说,会比较复杂,因为当插入的数据而对应新增的

Entry让B+树节点容纳不下时(即发生上溢),会触发分裂操作,而分裂操作则会导致生成新的

B+树节点,这就需要操作对应的父节点的孩子指针,以满足父节点Entry和孩子指针的有序性,同

时如果这个新增的节点会导致这个父节点也上溢的话就需要递归地进行分裂操作。

为了实现这一点,最简单的方法是每个B+树节点都维护一个父指针指向它的父亲,这样当分裂出

新的节点时就可以通过这个父指针获取对应的父节点,获取到之后就可以对这个父节点的孩子指针

进行相应的操作了。

这个方法虽然简单,但是在空间上会有一点额外的损耗,比如在32位机器上,一个指针的大小是4

字节,假如一棵B+树有N个节点,那么因为维护整个父指针就会额外损耗 4 * N 字节的空间

那么有没有什么办法既可以不需要父指针,又可以完成这个分裂操作呢?答案是利用返回值,当子

节点分裂出新的节点时,可以将这个节点返回,因为插入操作也是自顶向下按层进行的,所以对应

的父节点可以通过返回值拿到这个新增的节点,然后再进行对应的孩子指针的操作就可以了。

而如果在插入的时候没有触发分裂操作,这个时候我们只需要返回 null 即可,这样也相当于告诉了

父节点,下面没有发生分裂,所以父节点就自然不可能再触发分裂操作了。

由于数据是要插入在叶节点里面的,所以最开始一定是叶节点开始分裂,分裂出新的节点之后再向

上传递,所以我们先从叶节点的分裂操作开始介绍:

        protected boolean isFull() {return entries.size() == KEY_UPPER_BOUND;}@Overridepublic BPlusTreeNode insert(K entry, E value) {int equalEntryIndex = getEqualEntryIndex(entry);if (equalEntryIndex != -1) {data.get(equalEntryIndex).add(value);return null;}int index = findEntryIndex(entry);if (isFull()) {BPlusTreeLeafNode newLeafNode = split();int medianIndex = getMedianIndex();if (index < medianIndex) {entries.add(index, entry);data.add(index, asSet(value));} else {int rightIndex = index - medianIndex;newLeafNode.entries.add(rightIndex, entry);newLeafNode.data.add(rightIndex, asSet(value));}return newLeafNode;}entries.add(index, entry);data.add(index, asSet(value));return null;}

首先,我们先判断如果之前的叶节点就有这个Entry,那么我们直接将数据插入这个Entry对应的数

据集里面就可以了,同时由于Entry数量没有发生变化,所以肯定不会发生分裂,直接返回null即

可。

其次,如果没有发生上溢(isFull()返回false),则我们插入对应的Entry,再添加对应的数据即可。

最后,如果发生了上溢,则我们需要进行分裂操作:

        private BPlusTreeLeafNode split() {int medianIndex = getMedianIndex();List<K> allEntries = entries;List<Set<E>> allData = data;this.entries = new ArrayList<>(allEntries.subList(0, medianIndex));this.data = new ArrayList<>(allData.subList(0, medianIndex));List<K> rightEntries = new ArrayList<>(allEntries.subList(medianIndex, allEntries.size()));List<Set<E>> rightData = new ArrayList<>(allData.subList(medianIndex, allData.size()));BPlusTreeLeafNode newLeafNode = new BPlusTreeLeafNode(rightEntries, rightData);newLeafNode.next = this.next;this.next = newLeafNode;return newLeafNode;}

简单说,分裂就是插入这个数据及其对应的Entry之后,将这个节点的Entry和相应指针一分为二,

一半继续留在这个节点,另一半生成一个新的节点来容纳它们,同时更新一下next指针的指向。

叶节点分裂完之后会将分裂的信息(如果没有分裂则返回null,已经分裂了就返回这个新生成的叶

节点)

通过返回值传递给父节点,即非叶节点,所以下面我们继续介绍非叶节点的插入操作:

        @Overridepublic BPlusTreeNode insert(K entry, E value) {BPlusTreeNode newChildNode = children.get(findChildIndex(findEntryIndex(entry), entry)).insert(entry, value);if (newChildNode != null) {K newEntry = findLeafEntry(newChildNode);int newEntryIndex = findEntryIndex(newEntry);if (isFull()) {BPlusTreeNonLeafNode newNonLeafNode = split();int medianIndex = getMedianIndex();if (newEntryIndex < medianIndex) {entries.add(newEntryIndex, newEntry);children.add(newEntryIndex + 1, newChildNode);} else {int rightIndex = newNonLeafNode.findEntryIndex(newEntry);newNonLeafNode.entries.add(rightIndex, newEntry);newNonLeafNode.children.add(rightIndex, newChildNode);}newNonLeafNode.entries.remove(0);return newNonLeafNode;}entries.add(newEntryIndex, newEntry);children.add(newEntryIndex + 1, newChildNode);}return null;}

由于数据是插入在叶节点中,所以在非叶节点中我们只需要处理有新的孩子节点生成的情况,而新

生成的孩子节点又可以分为两种情况:

一是加入新生成的孩子节点之后没有发生上溢,这个时候只需要维护一下Entry和孩子指针,保持

其有序性即可。

二是加入新生成的孩子节点之后发生了上溢,这个时候跟叶节点类似,我们需要生成一个新的非叶

节点,插入这个新的子节点及其对应的Entry之后,将这个节点的Entry和相应的孩子指针一分为

二,一半继续留在这个节点,另一半生成一个新的非叶节点来容纳它们:


private BPlusTreeNonLeafNode split() {int medianIndex = getMedianIndex();List<K> allEntries = entries;List<BPlusTreeNode> allChildren = children;this.entries = new ArrayList<>(allEntries.subList(0, medianIndex));this.children = new ArrayList<>(allChildren.subList(0, medianIndex + 1));List<K> rightEntries = new ArrayList<>(allEntries.subList(medianIndex, allEntries.size()));List<BPlusTreeNode> rightChildren = new ArrayList<>(allChildren.subList(medianIndex + 1, allChildren.size()));return new BPlusTreeNonLeafNode(rightEntries, rightChildren);}

这里的分裂跟叶节点的分裂是类似的,不同是非叶节点的分裂不需要维护next指针。

删除(remove)

B+树的删除操作我觉得可以算是B+树中实现起来最复杂的操作,因为当删除发生下溢时,会涉及

到向兄弟节点借数据,同时还会涉及到合并两个相邻的节点。

在B+树的某些工业级实现中,删除可能是仅仅通过增加一个删除标记来实现,因为大多数数据的

变化比较平衡,尽管有时会出现下溢的情况,但这个节点可能很快就会增长以至于不再下溢,而且

这样还可以节约空间释放过程的成本,提高整个删除操作的效率。

但是考虑到本文主要侧重于对B+树的理解,所以这里的删除操作,我们仍然使用向兄弟节点借数

据和合并相邻节点的方式来进行处理。

与插入操作类似,我们在进行删除后可以将删除结果通过返回值的形式返回给父节点,父节点就可

以根据这个信息判断自身会不会因此发生下溢从而进行相应的操作。

在删除信息中,我们一般想知道两点信息:1.是否删除成功;2.子节点删除完成之后是否发生下

溢。

由于返回时要返回这两点信息,所以我们可以封装一个删除结果类:

    private static class RemoveResult {public boolean isRemoved;public boolean isUnderflow;public RemoveResult(boolean isRemoved, boolean isUnderflow) {this.isRemoved = isRemoved;this.isUnderflow = isUnderflow;}}

如果对是否删除成功不敢兴趣的话,在删除中就可以只返回一个布尔变量,以此向父节点传递该节点是

否下溢的信息。

同样的,由于数据都是在叶节点中,所以在删除数据时,下溢一定最先发生在叶节点中,所以我们

先从叶节点中的删除操作进行介绍。

        protected boolean isUnderflow() {return entries.size() < UNDERFLOW_BOUND;}@Overridepublic RemoveResult remove(K entry) {int entryIndex = getEqualEntryIndex(entry);if (entryIndex == -1) {return new RemoveResult(false, false);}this.entries.remove(entryIndex);this.data.remove(entryIndex);return new RemoveResult(true, isUnderflow());}

首先,如果我们在B+树中没有找到要删除的数据,那么我们直接返回即可,由于删除操作没有实

际发生,所以肯定也不会产生下溢。

然后,我们可以发现,在叶节点中,删除数据之后,并没有真正地去处理下溢,而只是简单地将该

节点目前是否下溢的信息的传递给父节点。

这是因为当下溢发生时,会涉及到节点的合并,而节点的合并会影响到父节点的Child指针,同时

由于父节点可以通过Child指针轻松访问到子节点,而子节点没有可以直接拿到父节点的方式,所

以综合这两点,下溢的处理交给父节点的比较合适的。

由于叶节点只可能存在于最后一层,所以任何节点的父节点都一定是非叶节点,下面我们来介绍非

叶节点的删除操作:

        @Overridepublic RemoveResult remove(K entry, E value) {int entryIndex = findEntryIndex(entry);int childIndex = findChildIndex(entryIndex, entry);BPlusTreeNode childNode = children.get(childIndex);RemoveResult removeResult = childNode.remove(entry, value);if (!removeResult.isRemoved) {return removeResult;}if (removeResult.isUnderflow) {this.handleUnderflow(childNode, childIndex, entryIndex);}return new RemoveResult(true, isUnderflow());}

非叶节点的整体处理逻辑比较简单,当没有删除成功时,我们直接将删除失败的结果向上传递即

可。

如果删除成功,则我们需要判断子节点是否发生下溢,如果发生下溢,则需要处理这个下溢,下面

是下溢的处理过程:

        private void handleUnderflow(BPlusTreeNode childNode, int childIndex, int entryIndex) {BPlusTreeNode neighbor;if (childIndex > 0 && (neighbor = this.children.get(childIndex - 1)).entries.size() > UNDERFLOW_BOUND) {//如果左边的邻居可以借childNode.borrow(neighbor, this.entries.get(reviseEntryIndex(entryIndex)), true);this.entries.set(reviseEntryIndex(entryIndex), childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(childNode) : childNode.entries.get(0));} else if (childIndex < this.children.size() - 1 && (neighbor = this.children.get(childIndex + 1)).entries.size() > UNDERFLOW_BOUND) {//如果右边的邻居可以借childNode.borrow(neighbor, this.entries.get(entryIndex), false);this.entries.set(entryIndex, childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(neighbor) : neighbor.entries.get(0));} else {//左右邻居都借不了就只能合并相邻节点了if (childIndex > 0) {// combine current child to left childneighbor = this.children.get(childIndex - 1);neighbor.combine(childNode, this.entries.get(reviseEntryIndex(entryIndex)));this.children.remove(childIndex);} else {// combine right child to current childneighbor = this.children.get(childIndex + 1);childNode.combine(neighbor, this.entries.get(entryIndex));this.children.remove(childIndex + 1);}this.entries.remove(reviseEntryIndex(entryIndex));}}

下溢的处理的大体流程也比较简单,首先先尝试向左邻居借,左邻居不能借就向右邻居借,如果右

邻居不能借就意味着已经没有邻居可以借给它了,所以这个时候就只能进行合并了。

合并时有一个小细节需要注意,就是如果这个节点是第一个节点,那么就只能把这个节点的右邻居

合并过来(因为它没有左邻居),否则我们就可以将左邻居合并过来

(对于最后一个节点也如此)。

下面我们看看具体的借数据以及合并是如何实现的,首页是叶节点:

        @Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeLeafNode leafNode = (BPlusTreeLeafNode) neighbor;int borrowIndex;if (isLeft) {borrowIndex = leafNode.entries.size() - 1;this.entries.add(0, leafNode.entries.get(borrowIndex));this.data.add(0, leafNode.data.get(borrowIndex));} else {borrowIndex = 0;this.entries.add(leafNode.entries.get(borrowIndex));this.data.add(leafNode.data.get(borrowIndex));}leafNode.entries.remove(borrowIndex);leafNode.data.remove(borrowIndex);}@Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeLeafNode leafNode = (BPlusTreeLeafNode) neighbor;this.entries.addAll(leafNode.entries);this.data.addAll(leafNode.data);this.next = leafNode.next;}

借数据的话我们只需要判断这个数据是从左邻居借来的还是从右邻居借来的,如果是从左邻居借来

的,根据Entry的有序性,我们需要把左邻居的最后一个Entry接出来作为当前节点的第一个Entry,

而从右邻居借来的刚好相反,需要把右邻居的第一个Entry借出来作为当前节点的最后一个Entry

(因为Entry都是从左到右依次增大的)。

叶节点的合并也比较简单,就是把邻居的Entry和数据都添加过来然后再维护一下next指针即可,

不过需要注意的是合并时仍然需要保持有序性,所以如果是合并左邻居,那么就需要用左邻居来调

用combine方法,否则如果合并的是右邻居,那么就需要当前节点来调用combine方法。

下面我们来看非叶节点的借数据和合并是如何实现的:

        @Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeNonLeafNode nonLeafNode = (BPlusTreeNonLeafNode) neighbor;if (isLeft) {this.entries.add(0, parentEntry);this.children.add(0, nonLeafNode.children.get(nonLeafNode.children.size() - 1));nonLeafNode.children.remove(nonLeafNode.children.size() - 1);nonLeafNode.entries.remove(nonLeafNode.entries.size() - 1);} else {this.entries.add(parentEntry);this.children.add(nonLeafNode.children.get(0));nonLeafNode.entries.remove(0);nonLeafNode.children.remove(0);}}@Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeNonLeafNode nonLeafNode = (BPlusTreeNonLeafNode) neighbor;this.entries.add(parentEntry);this.entries.addAll(nonLeafNode.entries);this.children.addAll(nonLeafNode.children);}

与叶节点不同,非叶节点的借数据和合并操作都会涉及到一个父节点的Entry,因为在非叶节点

中,Entry是从左边的节点到 父Entry 再到右边的节点依次增大的,如下图所示的两层非叶节点,

Entry的顺序是从左节点的13 到父Entry的23 再到右节点的31、43依次增大。

如果我们直接把邻居的Entry借过来的话,则会破坏Entry的有序性,比如直接把第二个节点的31借

过来,就变成了13 31 23,破坏了有序性(即23的第一个孩子指针指向的节点包含了比当前Entry

更大的Entry,这是与B+树特征相违背的)。

所以为了依然能够保证Entry的有序性,在非叶节点进行借数据操作时:

如果是向左邻居借,则我们应该先把父Entry借过来作为当前节点的第一个Entry,然后把左邻居的

最后一个Entry借过来填补父Entry的位置;

如果是向右邻居借,则我们应该先把父Entry借过来作为当前节点的最后一个Entry,然后把左邻居

的第一个Entry借过来填补父Entry的位置。

同样的道理,在非叶节点进行合并操作时,为了保证有序性,我们依然要先加入父节点,然后再添

加邻居的数据。

至此,B+树的增删查改四种操作就都介绍完了。

五、知识小结

本篇B+树的实现在存储上是直接基于内存的,不涉及到磁盘I/O,如果要改成基于外存的也并不

难,做一下叶节点和非叶节点的序列化,然后映射到磁盘上即可。相对于真实的基于外存的

B+树,基于内存的实现可以更简洁地表示出B+树的核心概念和方法,同时基于内存的B+树也可以

作为二叉搜索树的一种扩展,即多路搜索树。

相关文章:

04树 + 堆 + 优先队列 + 图(D1_树(D7_B+树(B+)))

目录 一、基本介绍 二、重要概念 非叶节点 叶节点 三、阶数 四、基本操作 等值查询(query) 范围查询(rangeQuery) 更新(update) 插入(insert) 删除(remove) 五、知识小结 一、基本介绍 B树是一种树数据结构&#xff0c;通常用于数据库和操作系统的文件系统中。 B树…...

MATLAB实现单层竞争神经网络数据分类

一.单层竞争神经网络介绍 单层竞争神经网络&#xff08;Single-Layer Competitive Neural Network&#xff09;是一种基于竞争学习的神经网络模型&#xff0c;主要用于数据分类和模式识别。其核心思想是通过神经元之间的竞争机制&#xff0c;使得网络能够自动学习输入数据的特…...

AITables首发:基于AI全自动推理设计数据库,国内首创,跑5分钟相当于架构师设计一周!

AITables仅运行5分钟&#xff0c;整个系统的表都设计好了&#xff01; 随着AI大模型技术的开源普及和平民化&#xff0c;现如今任何一个人都有可能成为超级个体。但随着企业级业务的膨胀和业务挑战增多&#xff0c;我们势必要跟上AI发展的节奏&#xff0c;让AI帮我们设计软件。…...

Go语言中结构体字面量

结构体字面量&#xff08;Struct Literal&#xff09;是在 Go 语言中用于创建和初始化结构体实例的一种语法。它允许你在声明结构体变量的同时&#xff0c;直接为其字段赋值。结构体字面量提供了一种简洁、直观的方式来创建结构体对象。 结构体字面量有两种主要形式&#xff1…...

PaddleOCR 截图自动文字识别

春节假期在家无聊&#xff0c;撸了三个小工具&#xff1a;PC截图编辑/PC录屏(用于meeting录屏)/PC截屏文字识别。因为感觉这三个小工具是工作中常常需要用到的&#xff0c;github上也有很多开源的&#xff0c;不过总有点或多或少的小问题&#xff0c;不利于自己的使用。脚本的编…...

【Blazor学习笔记】.NET Blazor学习笔记

我是大标题 我学习Blazor的顺序是基于Blazor University&#xff0c;然后实际内容不完全基于它&#xff0c;因为它的例子还是基于.NET Core 3.1做的&#xff0c;距离现在很遥远了。 截至本文撰写的时间&#xff0c;2025年&#xff0c;最新的.NET是.NET9了都&#xff0c;可能1…...

UE求职Demo开发日志#21 背包-仓库-装备栏移动物品

1 创建一个枚举记录来源位置 UENUM(BlueprintType) enum class EMyItemLocation : uint8 {None0,Bag UMETA(DisplayName "Bag"),Armed UMETA(DisplayName "Armed"),WareHouse UMETA(DisplayName "WareHouse"), }; 2 创建一个BagPad和WarePa…...

力扣988. 从叶结点开始的最小字符串

Problem: 988. 从叶结点开始的最小字符串 文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的先序遍历) 在先序遍历的过程中&#xff0c;用一个变量path拼接记录下其组成的字符串&#xff0c;当遇到根节点时再将其反转并比较大小&#xff08;字典顺序大小&…...

《PYTHON语言程序设计》(2018版)1.7近似π。利用步幅来进行修改

利用循环的步幅来计算派 利用正常的办法, pi 4 *(1-(1/3)(1/5)-(1/7)(1/9)-(1/11)(1/13)-(1/15)) print(pi)利用这段代码得出结果 我们如何利用循环来进行呢 一、思路 首先我们来利用excel表格来计算一下结果 我做了一个设想,让相加的部分先进行相加,然后再进行减法呢?? 结…...

低通滤波算法的数学原理和C语言实现

目录 概述 1 原理介绍 1. 1 基本概念 1.2 一阶RC低通滤波器模型 2 C语言完整实现 2.1 滤波器结构体定义 2.2 初始化函数 2.3 滤波计算函数 3 应用示例 3.1 噪声信号滤波 3.2 输出效果对比 3.3 关键参数选择指南 4 性能优化技巧 4.1 定点数优化 4.2 抗溢出处理 …...

【BUUCTF杂项题】荷兰宽带数据泄露、九连环

一.荷兰宽带数据泄露 打开发现是一个.bin为后缀的二进制文件&#xff0c;因为提示宽带数据泄露&#xff0c;考虑是宽带路由器方向的隐写 补充&#xff1a;大多数现代路由器都可以让您备份一个文件路由器的配置文件&#xff0c;软件RouterPassView可以读取这个路由配置文件。 用…...

安全策略实验报告

1.实验拓扑图 2.实验需求 vlan2属于办公区&#xff0c;vlan3生产区 办公区pc在工作日时间可以正常访问OAserver&#xff0c;i其他时间不允许 办公区pc可以在任意时间访问Web server 生产区pc可以在任意时间访问OA server但不能访问web server 特例&#xff1a;生产区pc可以…...

Haproxy+keepalived高可用集群,haproxy宕机的解决方案

Haproxykeepalived高可用集群&#xff0c;允许keepalived宕机&#xff0c;允许后端真实服务器宕机&#xff0c;但是不允许haproxy宕机&#xff0c; 所以下面就是解决方案 keepalived配置高可用检测脚本 &#xff0c;master和backup都要添加 配置脚本 # vim /etc/keepalived…...

亚博microros小车-原生ubuntu支持系列:20 ROS Robot APP建图

依赖工程 新建工程laserscan_to_point_publisher src/laserscan_to_point_publisher/laserscan_to_point_publisher/目录下新建文件laserscan_to_point_publish.py #!/usr/bin/env python3import rclpy from rclpy.node import Node from geometry_msgs.msg import PoseStam…...

Dockerfile构建容器镜像

Dockerfile 是一种文本格式的配置文件&#xff0c;用于自动化构建 Docker 镜像。它包含了一系列指令&#xff08;命令&#xff09;&#xff0c;每个指令定义了容器镜像构建过程中的一步操作。通过Dockerfile&#xff0c;我们可以指定基础镜像、安装依赖、配置环境变量、复制文件…...

python 在包含类似字符\x16、\x12、\x某某的数组中将以\x开头的字符找出来的方法

话不多说直接看例子&#xff1a; import re# 原始列表 data [\x16, \x17, s, \x16, hello, \x1A]# 正则表达式匹配以 \x 开头的字符串 pattern r^\\x# 找出以 \x 开头的字符 result [item for item in data if isinstance(item, str) and re.match(pattern, repr(item)[1:-…...

Spring Bean 的生命周期介绍

Spring Bean 的生命周期涉及多个阶段&#xff0c;从实例化到销毁&#xff0c;在开发中我们可以通过各种接口和注解介入这些阶段来定制化自己的功能。以下是详细的生命周期流程&#xff1a; 1. Bean 的实例化&#xff08;Instantiation&#xff09; 方式&#xff1a;通过构造函…...

调用腾讯云批量文本翻译API翻译srt字幕

上一篇文章介绍了调用百度翻译API翻译日文srt字幕的方法。百度翻译API是get方式调用&#xff0c;参数都放在ur中&#xff0c;每次调用翻译文本长度除了接口限制外&#xff0c;还有url长度限制&#xff0c;而日文字符通过ur转码后会占9个字符长度&#xff0c;其实从这个角度来讲…...

车载软件架构 --- 软件定义汽车面向服务架构的应用迁移

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…...

Baklib引领内容中台与人工智能技术的创新融合之路

内容概要 在数字化转型的浪潮中&#xff0c;各行业正在面临前所未有的挑战与机遇。内容中台作为一种新的概念&#xff0c;逐渐进入了企业的视野&#xff0c;它不仅是一个技术平台&#xff0c;更是提供了整合和管理内容的新思路。从根本上&#xff0c;内容中台旨在提升企业对信…...

想品客老师的第十一天:模块化开发

模块化概念 模块化开发可以提高代码的可维护性、可读性和复用性&#xff0c;同时降低开发和调试的复杂性&#xff0c;把业务根据功能分开写&#xff0c;解决变量命名的冲突&#xff0c;可以开放部分接口给类&#xff08;例如调用模块里的一个函数&#xff09;也更适合团队协作…...

接入DeepSeek大模型

接入DeepSeek 下载并安装Ollamachatbox 软件配置大模型 下载并安装Ollama 下载并安装Ollama&#xff0c; 使用参数ollama -v查看是否安装成功。 输入命令ollama list&#xff0c; 可以看到已经存在4个目录了。 输入命令ollama pull deepseek-r1:1.5b&#xff0c; 下载deepse…...

基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率

目录 1.算法仿真效果 2.算法涉及理论知识概要 3.MATLAB核心程序 4.完整算法代码文件获得 1.算法仿真效果 matlab2022a仿真结果如下&#xff08;完整代码运行后无水印&#xff09;&#xff1a; GA优化曲线&#xff1a; 优化前后星座图对比 优化前后误码率对比 仿真操作步骤…...

JavaScript系列(57)--工程化实践详解

JavaScript工程化实践详解 &#x1f3d7;️ 今天&#xff0c;让我们深入探讨JavaScript的工程化实践。良好的工程化实践对于构建可维护、高质量的JavaScript项目至关重要。 工程化基础概念 &#x1f31f; &#x1f4a1; 小知识&#xff1a;JavaScript工程化是指在JavaScript开…...

Linux-CentOS的yum源

1、什么是yum yum是CentOS的软件仓库管理工具。 2、yum的仓库 2.1、yum的远程仓库源 2.1.1、国内仓库 国内较知名的网络源(aliyun源&#xff0c;163源&#xff0c;sohu源&#xff0c;知名大学开源镜像等) 阿里源:https://opsx.alibaba.com/mirror 网易源:http://mirrors.1…...

【大数据技术】案例03:用户行为日志分析(python+hadoop+mapreduce+yarn+hive)

用户行为日志分析(python+hadoop+mapreduce+yarn+hive) 搭建完全分布式高可用大数据集群(VMware+CentOS+FinalShell) 搭建完全分布式高可用大数据集群(Hadoop+MapReduce+Yarn) 本机PyCharm远程连接虚拟机Python 搭建完全分布式高可用大数据集群(MySQL+Hive)...

LeetCode 0680.验证回文串 II:两侧向中间,不同就试删

【LetMeFly】680.验证回文串 II&#xff1a;两侧向中间&#xff0c;不同就试删 力扣题目链接&#xff1a;https://leetcode.cn/problems/valid-palindrome-ii/ 给你一个字符串 s&#xff0c;最多 可以从中删除一个字符。 请你判断 s 是否能成为回文字符串&#xff1a;如果能…...

第二十章 存储函数

目录 一、概述 二、语法 三、示例 一、概述 前面章节中&#xff0c;我们详细讲解了MySQL中的存储过程&#xff0c;掌握了存储过程之后&#xff0c;学习存储函数则肥仓简单&#xff0c;存储函数其实是一种特殊的存储过程&#xff0c;也就是有返回值的存储过程。存储函数的参数…...

架构规划之任务边界划分过程中承接分配

架构师在边界划分的过程中需要做什么事情呢&#xff1f;接下来&#xff0c;我们会讨论一些关于任务分配的 基础假设&#xff0c;以及由这些基础假设而带来的决策路径。 所谓任务边界划分&#xff0c;就是判定某个任务在多个承接方中&#xff0c;应该归属到哪个承接方的过程。…...

【C++】线程池实现

目录 一、线程池简介线程池的核心组件实现步骤 二、C11实现线程池源码 三、线程池源码解析1. 成员变量2. 构造函数2.1 线程初始化2.2 工作线程逻辑 3. 任务提交(enqueue方法)3.1 方法签名3.2 任务封装3.3 任务入队 4. 析构函数4.1 停机控制 5. 关键技术点解析5.1 完美转发实现5…...