Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Set.GetAt(index int) is int sufficient for index ? #44

Closed
axww opened this issue Oct 9, 2024 · 1 comment
Closed

Set.GetAt(index int) is int sufficient for index ? #44

axww opened this issue Oct 9, 2024 · 1 comment

Comments

@axww
Copy link

axww commented Oct 9, 2024

Hello,

First I want to thank you for making this awsome package.
I noticed an issue and this is only my personal assumption FYI.

btree.Set[type] type can be defined as 8 byte int64 or uint64.
In extreme situation, it can storage as much as 18446744073709551615 numbers into it, starts from 0, steps 1.
But for method Set.GetAt(index int), index is an int, also

if tr.root == nil || index < 0 || index >= tr.count {
	return tr.empty.key, tr.empty.value, false
}

On 32-bit machine, the maximum index value is 2147483647, not enough for above situation.
Do you consider change it into an interface{} that includes all Number types?

Thank you very much
Best regards

@axww axww changed the title Set.GetAt(index int) is it sufficient? Set.GetAt(index int) is int sufficient for index ? Oct 9, 2024
@tidwall
Copy link
Owner

tidwall commented Oct 9, 2024

I think using an int as the index type is sufficient for 32-bit programs.

Storing 2147483647 items in a B-tree would require each item to be at least 4 bytes to satsify a 32-bit range of ordering, where each item would be at a minimum an int32.

A B-tree that is completely filled with 2147483647 int32s will consume more than 8 GB of memory. This includes items and internal nodes.

A single process on a 32-bit machine cannot address more than 4GB of memory.

I believe your program will run out of memory before you get anywhere near 2147483647.

@axww axww closed this as completed Oct 9, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants