salmad3
commented
1 week ago [23-09-2024]:
Initial Thoughts for Specs
[!NOTE] TL;DR:
- Posts are being considered as the core primitive (one generic type).
- Boards are treated as a type of post with no parent to simplify the architecture.
- The system can use a slug hierarchy for efficient post organization and querying, allowing prefix-based searches to quickly identify relationships between posts and replies.
- AVL trees are implemented as the core data structure, ensuring balanced and efficient storage. However, concerns about title-based searches suggest supplementary structures might be necessary for non-hierarchical queries.
- While AVL trees perform well for insertions and lookups, managing everything in a single tree could lead to inefficiencies for complex queries. Multiple AVL trees or alternative structures may be used for different types of data (posts, comments).
- We will proceed with constructing the AVL tree based on the current Gno implementation and will assess its performance iteratively.
Context:
Discussions centered on how to structure boards and posts in a unified model, with posts as the base type for both. Treating boards as a type of post simplifies the architecture by allowing them to share common fields, such as slugs. Boards are differentiated by their parent-child relationships, where a board is simply a post without a parent.
Posts as a Universal Structure:
In this model, everything is treated as a post, including boards. Boards do not require a separate structure, as they are identified by their lack of a parent. Managing boards, posts, and replies uniformly reduces complexity and avoids the need for multiple types. Comments and sub-posts are children of a parent post, and each post can be rendered differently depending on its label or type.
[!NOTE] This unified structure reduces the overhead of maintaining multiple types and adds flexibility at the UI level by allowing different post behaviors.
Hierarchical Slug Design
The slug system is key to organizing the hierarchy. A slug like 0_blog could represent a board, while 0_blog:1_username1 represents the first post under that board. Additional nesting is handled by extending the slug (0_blog:1_username1:2_username2). This slug hierarchy allows efficient traversal and retrieval of posts and their replies using prefix-based queries. For instance, all replies to 0_blog:1_username1 can be fetched by querying slugs that start with that prefix.
Using prefix searches allows efficient iteration through all replies or sub-posts. This method eliminates the need for complex joins or additional structures for parent-child queries, leveraging the slug structure to quickly identify related posts.
// Example Slug System:
// "0_blog" > board
// "0_blog:1_username1" > post under blog board
// "0_blog:1_username1r:2_username2" > reply to username1's postIterating Through Posts Using Slugs
Example 1: Iteration Using Plain Slugs (courtesy of @jeronimoalbi)
When using plain slugs (no ID prefixes), we rely on string operations like HasPrefix to manage traversal and filtering. This approach works but has limitations, especially in knowing when to stop the iteration.
start := "blog"
tree.Iterate(start, "", func(slug string, _ interface{}) bool {
if !strings.HasPrefix(slug, start) {
return true // Stop when slug no longer matches the prefix
}
println(" > " + slug) // Output: "blog", "blog/a", "blog/a/1", etc.
return false
})Without a clear end point, we manually check if each item's slug still matches the prefix, which can be inefficient.
Example 2: Iteration Using ID Prefixes (courtesy of @jeronimoalbi)
By adding ID prefixes to slugs (e.g., 1_blog), we can identify iteration boundaries more effectively. This allows for simpler and more efficient traversal without needing string operations like HasPrefix.
start := "1_" // ID is used as the start instead of slug
end := "2" // End is expressed as string(ID+1)
tree.Iterate(start, end, func(slug string, _ interface{}) bool {
println(" > " + slug) // Output: "1_blog", "1_blog/a", "1_blog/b", etc.
return false
})Using ID prefixes allows iteration to be more efficient, as it avoids the need for string matching checks at each step.
AVL Tree as the Core Data Structure
The AVL tree is proposed as the primary data structure for storing posts, keyed by the slug. This ensures that all posts are stored in a balanced and efficient manner.
Although AVL trees offer O(log n) complexity for insertions and searches, concerns were raised about their efficiency for title-based searches. Searching for a post by its title would require traversing the entire tree, which is inefficient for large datasets.
[!WARNING] Global searches, particularly for non-slug fields like titles, might introduce inefficiencies especially for large datasets.
Handling Global Search
Title-based searches across the AVL tree are inefficient. Supplementary structures or inverted indexes are considered for fast lookups by title or other non-hierarchical fields. The slug structure remains useful for hierarchical queries, while additional indexing will handle broader searches.
Differentiating Boards and Posts in Practice
Structurally, boards and posts are identical as posts. They can be distinguished by labels or type fields. For instance, boards can have the label "board", while posts might carry a different label. This distinction allows the UI to handle boards, threads, and comments differently, providing system behavior flexibility.
Iteration & Data Access
Efficient iteration is crucial, especially when accessing data chunks. All posts and sub-posts should be retrievable without multiple calls when iterating through a board. This is achievable by iterating over the slug hierarchy, using the prefix to access relevant posts quickly. AVL tree traversal allows for chunked access, ensuring that only relevant data is loaded, which optimizes performance.
Constraints of a Single AVL Tree
Managing everything in a single AVL tree can lead to inefficiencies. Handling different aspects of the hierarchy (boards, posts, comments) within a single tree might not scale well, especially for complex queries like global title searches. The use of multiple AVL trees—one for each level of the hierarchy—or separate trees for posts and comments is being considered to improve performance.
[!TIP] Multiple AVL trees could be necessary to optimize data handling, improving performance by distributing the load across different trees for specific types of queries.
Complexity Analysis:
[!WARNING] This assumes the implementation in gno.land and needs checking
Summary of Time Complexity
| Operation | AVL Tree | With ID Prefixes | Global Search (Title) |
|---|---|---|---|
| Insertion | O(log n) | O(log n) | O(log n) |
| Search (Slug) | O(log n) | O(log n) | O(n) |
| Iteration | O(n * m) | O(n) | O(n) |
Summary of Space Complexity
| Structure | Space Complexity |
|---|---|
| AVL Tree | O(n) |
| Slug Structure | O(n) |
Context:
For basic operations like insertion and search, we use an AVL tree as our core data structure. AVL trees are designed to remain balanced, which means their height is always logarithmic in proportion to the number of nodes. This is why insertion and search take O(log n) time. Every time a new post is added or searched for, the AVL tree needs to rebalance itself to ensure efficient future operations.
When iterating through posts using plain slugs (without ID prefixes), the system needs to compare each post's slug with a target prefix (using something like HasPrefix). This adds a bit of overhead because it involves comparing strings, which can vary in length (denoted by m). So, if we're dealing with 1,000 posts and the slugs are 10 characters long on average, we're looking at O(n * m) time complexity.
The idea behind ID prefixes is to speed up this process. If every post’s slug has a unique numeric prefix (like 1_blog, 2_blog, etc.), the system can simply iterate through these posts in O(n) time, without needing to compare strings. It knows where to start and stop based on the IDs, making traversal faster.
Then, global searches, like looking for a post by its title, present more of a challenge with AVL trees. Since the tree is organized by slugs, not titles, you’d have to traverse the entire tree to check each title. This takes O(n) time. This inefficiency is why we mentioned possibly adding supplementary structures for fields like titles in the future. But, without them, a title search in an AVL tree is linear.
jefft0
Context:
Tracking issue for specification efforts for boards v2.
Related Notes & Links:
/r/demo/boards/v2