Comments (2)
I did not consider this range search interface closely. But the implementation is quite simple. Since the keys strored in leaf nodes have been sorted, once you get the first element of the leaf node, you can traverse the next leaves until it touches the upside of the range given. The leaves traversed are what you need to query. Therefore it is an O(n) query algorithm.
from bplustree.
Thanks for your provided solution. I found it has been shown how to do range search. the code following in bplus_tree_get_range
commened with 'here is the iteration' is the iteration method.
long bplus_tree_get_range(struct bplus_tree *tree, key_t key1, key_t key2)
{
long start = -1;
key_t min = key1 <= key2 ? key1 : key2;
key_t max = min == key1 ? key2 : key1;
struct bplus_node *node = node_seek(tree, tree->root);
while (node != NULL) {
int i = key_binary_search(node, min);
if (is_leaf(node)) {
if (i < 0) {
i = -i - 1;
if (i >= node->children) {
node = node_seek(tree, node->next);
}
}
// here is the iteration.
while (node != NULL && key(node)[i] <= max) {
start = data(node)[i];
if (++i >= node->children) {
node = node_seek(tree, node->next);
i = 0;
}
}
break;
} else {
if (i >= 0) {
node = node_seek(tree, sub(node)[i + 1]);
} else {
i = -i - 1;
node = node_seek(tree, sub(node)[i]);
}
}
}
return start;
}
I will close this issue.
from bplustree.
Related Issues (15)
- a segment fault HOT 1
- 执行./coverage_build.sh 提示 node_seek: Assertion `len == _block_size' failed. HOT 21
- 支持单用户写入,多用户查询吗? HOT 8
- in-memory 分支 bplus_tree_get_range 有bug HOT 1
- in-memory 版本在析构树时内存泄露 HOT 2
- excute coverage_build.sh failed in macos HOT 7
- add some code annotation in head file(bplustree.h) HOT 1
- 分裂策略是否有问题? HOT 3
- Is there any way to restore the transactions from the database when the program is broken? HOT 2
- It seems the non_leaf_split_right1 function has a bug. HOT 1
- 请问value可以自定义类型吗? HOT 6
- 请问可以直接在C++里使用这个代码吗? HOT 3
- 请教一个问题bplus_tree_insert内部函数的实现 HOT 12
- 执行demo_build.sh 提示 statement may fall through HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bplustree.