Quick answers:
- A tree:
Each node has 8 children, top-back-left, top-back-right, etc. down to a certain level
The code for this can get quite complex, especially if the voxels can change at runtime. - The type of voxel (colour, material, a list of items)
- yep. Cubes only
More specifically 1x1, 2x2, 4x4, 8x8 etc. It must be an entire node.
If you really want to you could define some sort of patterns, but its no longer a octdtree. - yeah, but it depends on your data. Imagine describing 256 identical blocks individually, or describing it once (like air in Minecraft)
I'd start with trying to understand quadtrees first. You can do that on paper, or make a test program with it. You'll answer these questions yourself if you experiment