Taxonomy or database table?
You don't need any changes to your database, with HS Or SHS you already store enough data to built a template answering your needs.

From my point of view, once your view is configured, you can alter the display of your field while overriding the default TPL file.

From the view edit page, if you go into "Theme: Information", you can find the name of the file you need to create and place into your theme folder.

The file name should look like this:

views-view-field--name-of-your-view--name-of-your-field.tpl.php

As a base for you file, you should use views-view-field.tpl.php (located in sites/all/modules/views/theme). In that template, there's some variables available to help you build what you want (like $row or $field).

If you have Hierarchical Select installed, you can simply render the field, it will display data the way you want.

Here's some untested code:

$field = field_view_field('entity_name', $fully_loaded_entity, 'your_field_name'); 
print render($field);


For that chunck of code to work, you need to specify if you're working with a node, user or term, pass the loaded entity and give the corresponding field name.

The rendered HTML should be enough to build something like this (made with the exact same method):